Approximate string matching: A simpler faster algorithm

Richard Cole; Ramesh Hariharan

Approximate string matching: A simpler faster algorithm

Richard Cole, Ramesh Hariharan

Computer Science

Research output: Contribution to conference › Paper › peer-review

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(nk³/m+n+m) on all patterns except mostly periodic strings (defined later). The second algorithm runs in time O(nk⁴/m+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

Original language	English (US)
Pages	463-472
Number of pages	10
State	Published - 1998
Event	Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 25 1998 → Jan 27 1998

Other

Other	Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
City	San Francisco, CA, USA
Period	1/25/98 → 1/27/98

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{58123ad0fdc64ae08dc6831fa2d97855,

title = "Approximate string matching: A simpler faster algorithm",

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(nk3/m+n+m) on all patterns except mostly periodic strings (defined later). The second algorithm runs in time O(nk4/m+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.",

author = "Richard Cole and Ramesh Hariharan",

year = "1998",

language = "English (US)",

pages = "463--472",

note = "Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1998 Through 27-01-1998",

}

TY - CONF

T1 - Approximate string matching

T2 - Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms

AU - Cole, Richard

AU - Hariharan, Ramesh

PY - 1998

Y1 - 1998

N2 - 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(nk3/m+n+m) on all patterns except mostly periodic strings (defined later). The second algorithm runs in time O(nk4/m+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

AB - 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(nk3/m+n+m) on all patterns except mostly periodic strings (defined later). The second algorithm runs in time O(nk4/m+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

UR - http://www.scopus.com/inward/record.url?scp=0032256006&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032256006&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032256006

SP - 463

EP - 472

Y2 - 25 January 1998 through 27 January 1998

ER -

Approximate string matching: A simpler faster algorithm

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this