The idea: race two matchers on the same text
Both rows show the same text T (length n) with the pattern P (length m) under it. The pattern sits at a shift s: P[0] is under T[s]. Each row runs its own algorithm, and both run at the same time: every animation step does one comparison on the top row and one on the bottom row. After k steps both have done the same amount of work, so you can see which one has got further through the text. A row that finishes shows "finished" and waits for the other.
Every algorithm finds all occurrences, so after a match it keeps going. The counters under each row are the character comparisons, the shifts (how often the pattern moved) and the matches. Text is limited to 40 characters and the pattern to 12, so both fit on the canvas; spaces are drawn as ␣.
What one step is
| Algorithm | One step | Shift after a mismatch |
|---|---|---|
| Naive | compare T[s+j] with P[j], left to right | always 1 |
| KMP | compare T[i] with P[j], left to right | j − lps[j−1]; the text position i never moves back |
| Boyer-Moore | compare T[s+j] with P[j], right to left | max(bad character, good suffix) |
| Horspool | compare right to left | shift[c] for c = the window's last character |
| Rabin-Karp | compare the window hash with the pattern hash, or (after a hash hit) one character | always 1, with a rolling-hash update |
The tables under each row are built before the race and are not counted. Building them is cheap: O(m) for lps and good suffix, O(m + alphabet) for the character tables.
Naive (brute force)
Try every shift s = 0, 1, …, n − m and compare left to right until a mismatch. Nothing learned in one window is used in the next, so a text of A's with the pattern AAAAAB costs m comparisons at every shift: (n − m + 1) · m in the worst case. Demo: AAAA...AB worst case — 150 comparisons against KMP's 54.
KMP and the lps table
lps[j] is the length of the longest proper prefix of P[0..j] that is also a suffix of it. After a mismatch with j characters matched, those j characters are known: they are P[0..j−1]. Their longest border, lps[j−1], is the most that can still be matched, so KMP slides the pattern so that lps[j−1] characters stay matched (blue on the canvas, not read again) and goes on comparing at the same text position. Every comparison either moves the text position forward or moves the pattern forward, so there are at most 2n comparisons.
For ABABAC the table is 0 0 1 2 3 0. Demo: self-overlap ABABAC: after ABABA matches and the next character is B instead of C, lps[4] = 3 keeps ABA matched — 27 comparisons against naive's 57. The single-algorithm page KMP String Matching shows how the table is built.
Boyer-Moore: bad character and good suffix
Boyer-Moore compares from the right end of the pattern. When T[s+j] = c does not match P[j]:
- Bad character: line c up with its rightmost occurrence in P, a shift of j − last[c]. If c is not in P at all, last[c] = −1 and the whole pattern jumps past it.
- Good suffix: the part P[j+1..m−1] that did match must line up with another copy of itself in P (or a prefix of P that is a suffix of it). gs[j] is that shift; gs[0] is also the shift after a full match.
![Boyer-Moore searching for that in find that word: at shift 0 the last pattern character t meets d, which is not in the pattern, so the pattern jumps 4; at shift 4 it meets a, which is P[2], so it shifts 1; at shift 5 all four characters match from right to left](Images/stringsearchrace/boyer-moore.svg)
The shift is the larger of the two. On English text most characters of the text are not in a short pattern, so Boyer-Moore reads only a fraction of the text: Demo: English sentence — 15 comparisons against KMP's 33 for "at that" in a 35-character sentence. It can be slow on highly repetitive input, though: with 22 overlapping matches of AAA, it re-reads 3 characters at every shift (66 against KMP's 24, Demo: many matches). The Galil rule fixes that and is left out here.
Horspool
Horspool keeps only a character table: after any mismatch or match, shift by shift[c], where c is the text character under the last position of the pattern. It is simpler and fast on large alphabets, but without the good-suffix rule it shifts less on small alphabets. Demo: Boyer-Moore vs Horspool: 16 against 26 comparisons on a three-letter text. Demo: no match: Horspool reads 10 characters of a 39-character sentence; naive reads 37.
Rabin-Karp and spurious hits
Rabin-Karp reads each window as a number in base 256 (the ASCII codes) modulo a prime q. The next window's hash comes from the previous one in constant time: drop the left character, add the right one (the rolling hash). Only when the window hash equals the pattern hash are the characters compared. Equal hashes with different strings are spurious hits; the smaller q, the more of them. Demo: spurious hits: with q = 11 there are 5 spurious hits (41 steps); with q = 997 none (35 steps). Real implementations use a large q (about 109), so spurious hits are rare and the expected cost is O(n + m).
Summary
| Algorithm | Preprocessing | Worst case (all matches) | Typical |
|---|---|---|---|
| Naive | none | O(n m) | about n on random text |
| KMP | O(m) | ≤ 2n comparisons | about n |
| Boyer-Moore | O(m + alphabet) | O(n m) without the Galil rule | about n / m on large alphabets |
| Horspool | O(m + alphabet) | O(n m) | about n / m on large alphabets |
| Rabin-Karp | O(m) | O(n m) if every window is a hit | O(n + m) expected |
What the page leaves out
- The cost of building the tables, and the time per comparison: a Rabin-Karp hash step is more work than a character comparison.
- The Galil rule for Boyer-Moore and other variants (Turbo-BM, Sunday, Two-Way), and multi-pattern search (Aho-Corasick).
- Unicode: the inputs are cut to printable ASCII.
See also KMP String Matching (how the lps table is built), Binary and Linear Search, and Grid Pathfinding Side by Side, another race between two algorithms.