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 k-break periodic strings (defined later). The second algorithm runs in time O(nk4/m + n + m) on k-break periodic patterns. The two classes of patterns are easily distinguished in O(m) time.
Original language | English (US) |
---|---|
Pages (from-to) | 1761-1782 |
Number of pages | 22 |
Journal | SIAM Journal on Computing |
Volume | 31 |
Issue number | 6 |
DOIs | |
State | Published - Sep 2002 |
Keywords
- Algorithms
- Edit distance
- String matching
ASJC Scopus subject areas
- Computer Science(all)
- Mathematics(all)