KMP search
The naive search slides the pattern one place after every mismatch and re-reads letters it has already seen. KMP first works out, for every prefix of the pattern, how much of it repeats at its own start. After a mismatch it slides the pattern straight to the next place that could still match, and never moves backwards in the text.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| text | a | b | a | c | a | b | a | b | c | a | b | a | b |
| pattern | a | b | a | b |
fail[i]: the longest proper prefix of the pattern that also ends at position i
0 a
1 b
2 a
3 b
Find every place "abab" appears in "abacababcabab". First, study the pattern on its own.
1function kmpSearch(text, pat) {2 const fail = new Array(pat.length).fill(0);3 for (let i = 1, k = 0; i < pat.length; i++) {4 while (k > 0 && pat[i] !== pat[k]) k = fail[k - 1];5 if (pat[i] === pat[k]) k++;6 fail[i] = k;7 }8 const hits = [];9 for (let i = 0, j = 0; i < text.length; i++) {10 while (j > 0 && text[i] !== pat[j]) j = fail[j - 1];11 if (text[i] === pat[j]) j++;12 if (j === pat.length) {13 hits.push(i - j + 1);14 j = fail[j - 1];15 }16 }17 return hits;18}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n + m | m to build the table, n to search |
| average | n + m | any text and pattern |
| worst | n + m | where the naive search can take n · m |
| space | m | the failure table |
Where it breaks
- Repetitive text is where it shines. Pick Find aab: the naive search matches "aa" and fails at the third letter over and over, re-reading the same letters. KMP keeps the "a" it already matched and carries on.
- Overlapping matches. Pick Overlaps: "aa" appears 4 times in "aaaaa", sharing letters. After each hit KMP falls back through the table rather than restarting, so it finds them all.
- The table is the hard part. Building it uses the same idea as the search, matching the pattern against itself. Getting
fail[k − 1]and the loop bounds right is where most bugs live.