String Matching
Find a pattern inside a text. Brute force tries every position; Horspool, Boyer–Moore and Knuth–Morris–Pratt (KMP) study the pattern first so they can skip ahead. Count the character comparisons and see which one wins.
| algorithm | character comparisons | alignments | preprocessing steps | match at |
|---|
How to read this
The top row is the text T with its indices; the orange arrow marks the text character being compared. The row below is the pattern P, drawn where it is currently aligned. Green cells matched, red is the mismatch. A green bar above the text marks a match already found. Under the strings are the algorithm's precomputed tables; the highlighted entry is the one being written or looked up.
Counting. "Character comparisons" counts every test of a pattern character against a text character during the search. Table building is counted separately as "preprocessing steps" (for KMP these are character comparisons too). In KMP, the if re-tests the pair that stopped the while; that pair is counted once.
Try this
- The book example. With BAOBAB and Boyer–Moore, the shifts are 6, then max(4, 5) = 5 (good suffix wins), then max(5, 2) = 5 (bad symbol wins), then a match at index 16, as in Levitin §7.2. Compare 12 comparisons with brute force's 24.
- Brute force's worst case. Load "Brute-force worst case" (n = 25, m = 4). Brute force makes m(n − m + 1) = 88 comparisons. Which algorithm does best here, and why?
- Horspool can lose. Load "Text of zeros" (pattern 10000). Horspool compares all 5 characters before every 1-step shift: 180 comparisons, far more than brute force's 36 (Levitin Exercise 7.2.3). Boyer–Moore's good-suffix rule brings it back down to 40.
- Horspool's shift table by hand. For BARBER, predict t(A), t(B), t(E), t(R) before stepping through preprocessing. (4, 2, 1, 3; everything else is 6.)
- KMP never looks back. Load "Long borders" with KMP. Watch i: it only moves forward, and the total never exceeds 2n comparisons. Tick "find all matches" and see the pattern overlap itself.