## Abstract

We present a new algorithm for string matching, the technique which is extensively used in pattern recognition. The conventional dynamic programming algorithm of Wagner and Fischer [2] contains much unnecessary computation; its time complexity is O(mn), where m and n are the lengths of the strings to be compared. We develop a new bandwidth algorithm that confines the string editing operations within necessary limits, reducing time complexity to O(mn-(m-b)(m-b-1)), where b is the bandwidth and n ≥ m. The experimental results show that the running time of the bandwidth algorithm can be reduced to O(n) for similar strings.

Original language | English (US) |
---|---|

Pages (from-to) | 328-333 |

Number of pages | 6 |

Journal | Proceedings of the IEEE International Conference on Systems, Man and Cybernetics |

Volume | 1 |

State | Published - 1995 |

Event | Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can Duration: Oct 22 1995 → Oct 25 1995 |

## All Science Journal Classification (ASJC) codes

- Control and Systems Engineering
- Hardware and Architecture