Approximate String Matching: A Simpler Faster Algorithm

Content Provider	Indian Institute of Science (IISc)
Author	Cole, Richard Hariharan, Ramesh
Copyright Year	2000
Abstract	We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first algorithm, which is quite simple, runs in time $O(\frac{nk^3}{m}+n+m)$ on all patterns except k-break periodic strings (defined later). The second algorithm runs in time $O(\frac{nk^4}{m}+n+m)$ on k-break periodic patterns. The two classes of patterns are easily distinguished in O(m)time.
File Format	PDF
Journal	PeerReviewed
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2000-12-01
Access Restriction	Authorized
Subject Keyword	Computer Science & Automation (Formerly, School of Automation)
Content Type	Text
Resource Type	Article