Bandwidth algorithm for string matching

David T. Wang, Yi Zhao, Val Beskin, Douglas D.C. Hung, Daniel Y. Chao

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish (US)
Pages (from-to)328-333
Number of pages6
JournalProceedings of the IEEE International Conference on Systems, Man and Cybernetics
Volume1
StatePublished - 1995
EventProceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can
Duration: Oct 22 1995Oct 25 1995

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Bandwidth algorithm for string matching'. Together they form a unique fingerprint.

Cite this