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