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  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)|
|Number of pages||6|
|Journal||Proceedings of the IEEE International Conference on Systems, Man and Cybernetics|
|State||Published - Dec 1 1995|
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Hardware and Architecture