String Matching
Looking for a word in a text is sliding the word along and checking whether it fits. The naive way tries every position and re-reads characters after each failure. KMP first studies the pattern: for every prefix it records the longest border, a proper prefix that is also a suffix, so after a mismatch it knows how far the pattern can jump without missing a match and never re-reads the text. Rabin-Karp takes a different shortcut: it compares numbers instead of strings, a rolling hash of each window against the hash of the pattern, and only reads characters when the numbers agree. Manacher's algorithm answers a different question with the same machinery: the longest palindrome. Putting a separator in every gap makes even and odd palindromes one case, and a box around the palindrome that reaches furthest right lets most positions copy their radius from a mirror instead of comparing from scratch, which is what turns the obvious quadratic expansion into linear time.
Hash the pattern once: h("abra") = 57, using base 31 modulo 101. Then slide a window of 4 over the text, updating its hash in O(1) by dropping the leftmost character and adding the next. Characters are compared only when the two hashes agree.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
Window "abra" hashes to 57, the pattern to 57. What happens?
Answer: Hashes agree, verify: match. Equal hashes do not prove equality, so the characters are checked.
Window "brac" hashes to 57, the pattern to 57. What happens?
Answer: Hashes agree, verify: spurious hit. Two different strings can share a hash modulo 101.
Window "raca" hashes to 78, the pattern to 57. What happens?
Answer: Hashes differ, skip. Different hashes mean different strings, so nothing is read.
Window "acad" hashes to 90, the pattern to 57. What happens?
Answer: Hashes differ, skip. Different hashes mean different strings, so nothing is read.
Window "cada" hashes to 68, the pattern to 57. What happens?
Answer: Hashes differ, skip. Different hashes mean different strings, so nothing is read.
Window "adab" hashes to 39, the pattern to 57. What happens?
Answer: Hashes differ, skip. Different hashes mean different strings, so nothing is read.
Window "dabr" hashes to 19, the pattern to 57. What happens?
Answer: Hashes differ, skip. Different hashes mean different strings, so nothing is read.
Window "abra" hashes to 57, the pattern to 57. What happens?
Answer: Hashes agree, verify: match. Equal hashes do not prove equality, so the characters are checked.
How it runs, step by step
Hash the pattern once: h("abra") = 57, using base 31 modulo 101. Then slide a window of 4 over the text, updating its hash in O(1) by dropping the leftmost character and adding the next. Characters are compared only when the two hashes agree.
Rabin-Karp with pattern hash 57.
Shift 0, window "abra" hashes to 57. Equal to the pattern hash 57, and the characters agree: a match at index 0.
Match at 0.
Shift 1, window "brac" hashes to 57. Equal to the pattern hash 57, but the characters differ: a spurious hit, rejected.
Hash hit at 1, rejected.
Shift 2, window "raca" hashes to 78. Not 57, so the window cannot be the pattern and no characters are read.
Hash differs at 2.
Shift 3, window "acad" hashes to 90. Not 57, so the window cannot be the pattern and no characters are read.
Hash differs at 3.
Shift 4, window "cada" hashes to 68. Not 57, so the window cannot be the pattern and no characters are read.
Hash differs at 4.
Shift 5, window "adab" hashes to 39. Not 57, so the window cannot be the pattern and no characters are read.
Hash differs at 5.
Shift 6, window "dabr" hashes to 19. Not 57, so the window cannot be the pattern and no characters are read.
Hash differs at 6.
Shift 7, window "abra" hashes to 57. Equal to the pattern hash 57, and the characters agree: a match at index 7.
Match at 7.
Found at 0, 7. 8 windows, 3 verified character by character. Expected O(n + m); only a hash collision costs a wasted verification.
Matches at 0, 7.
Write it yourself
Define countOccurrences(text, pattern) and return how many times the pattern occurs, counting overlaps. It runs in your browser against this lesson's own 2 examples.
// Build the table of how far to fall back on a mismatch, so the text pointer never moves backwards.function countOccurrences(text, pattern) { return 0;}
Remember
- Naive matching is O(n x m) because a mismatch throws away characters already read.
- pi[i] is the longest border of the first i + 1 pattern characters; KMP jumps to pi[j - 1] on a mismatch.
- Rabin-Karp compares hashes in O(1) per window and verifies only on a hit; Manacher pads the string with separators and copies each radius from its mirror inside the current box.
Topics covered
Related
Where this is used
Developer toolsgrep and ripgrep
A literal search does not have to read every byte. Boyer-Moore compares the pattern right to left and, on a mismatch, slides the pattern so the offending text character lines up with its last occurrence in the pattern, which can skip nearly a whole pattern length at once; GNU grep is built on that skip. ripgrep goes further and scans for the rarest byte of the pattern with memchr, so most of the file is passed over by a vectorised byte scan and only candidate positions are compared in full.
SecurityIntrusion detection signatures
Snort and Suricata check every packet against thousands of byte patterns at line rate, so one search per signature is out of the question. They use Aho-Corasick, which is the prefix function built over a trie of all the patterns at once: a mismatch follows a failure link to the longest pattern prefix still alive, so the packet is read once no matter how many signatures are loaded. Suricata also ships Hyperscan as an alternative matcher for the same reason, trading preprocessing time for a single pass over the payload.
Backup and syncrsync and deduplicating backups
The receiver splits its copy of a file into blocks and sends their checksums; the sender then rolls a checksum across every offset of its own copy, looks each value up, and transmits only the blocks that never matched. That is the Rabin-Karp window, though rsync's weak checksum is an Adler-32 variant rather than a polynomial hash. Backup tools reuse the trick to cut chunks at content-defined boundaries: restic rolls a Rabin fingerprint over a 64 byte window and borg rolls a Buzhash, so inserting a byte near the start of a file shifts one chunk instead of every chunk after it. All of them need the hash to update in O(1) as the window slides, which is the whole point of the rolling form.
Standard librariesSubstring search in standard libraries
glibc's strstr and memmem use the two-way algorithm of Crochemore and Perrin, which splits the pattern at a critical position and keeps a linear worst case in constant extra space, unlike KMP's table that is as long as the pattern. CPython added the same algorithm in 3.10, and str.find and the in operator fall back to it when a search starts to look quadratic on a long string. A library call cannot afford to allocate on every search or to stall on a hostile string, which is what makes the more intricate preprocessing worth it.
Why it works this way
Why does a mismatch jump to pi[j - 1] instead of starting over?
The first j characters of the pattern have already matched the text, so the only alignments still worth trying are the ones where a prefix of the pattern lands on characters it is known to match: a prefix of the pattern that is also a suffix of those j characters, which is a border. pi[j - 1] is the longest border, so sliding to it is the smallest jump that cannot step over a match, and any smaller jump would need a longer border that pi says does not exist.
Why is KMP linear when the inner while loop can spin many times?
Count what happens to j rather than counting loop iterations. Each text character raises j by at most one, so over the whole text j gains at most n; every turn of the while loop strictly lowers j, and j never drops below zero, so those turns add up to at most n across the entire run. One character can trigger a long chain of fallbacks, but only because earlier characters paid for it.
In Rabin-Karp, equal hashes are not a match
The hash comparison is a filter, not an answer: different windows can share a hash, so the substring comparison after a hit is needed for correctness rather than as a safety check. A modulus as small as the 101 used above collides constantly, and every collision costs a full O(m) comparison, which is how the method degrades to O(n x m); real uses take a large prime modulus and a random base so an adversary cannot craft collisions. One more trap: the rolling step subtracts the outgoing character's contribution and that can go negative under a modulus, so add the modulus back before taking the remainder.
Manacher: why a separator in every gap, and why the mirror is capped
A palindrome of even length has no centre character, so without padding you need one pass for odd centres and another for the gaps between characters. Inserting '#' between every pair and at both ends makes every palindrome odd and centred on a real index, and the radius measured there equals the length of the palindrome in the original string. The copied value p[2 * c - i] has to be capped at r - i because the mirror's palindrome may run past the left edge of the current box, and outside the box nothing has been verified yet; the while loop is what extends past the edge, one pair at a time.
Read more
- Knuth-Morris-Pratt algorithmWikipedia
- Prefix function and the Knuth-Morris-Pratt algorithmcp-algorithms
- Rabin-Karp algorithm for string matchingcp-algorithms
- Manacher's algorithm: finding all sub-palindromes in O(n)cp-algorithms
- ripgrep is faster than grep, ag, git grep, ucg, pt and siftAndrew Gallant · burntsushi.net
Next up
- Aho-CorasickA trie of all patterns plus failure links; matches many patterns in one pass over the text.
- TrieA tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.
- Suffix ArrayThe starting indices of all suffixes, sorted; binary search finds substrings.