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.
Find the longest palindrome in "abacabad". A palindrome can have an even or an odd length, and that is two cases nobody wants to write twice, so put a # in every gap and at both ends: "#a#b#a#c#a#b#a#d#". Every palindrome in there is now odd, centred on one position, and its radius is exactly the length of the palindrome in the original text.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
What radius does position 4 start from, before any comparing?
Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 2) = 0. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 5 start from, before any comparing?
Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 1) = 1. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 8 start from, before any comparing?
Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 6) = 0. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 9 start from, before any comparing?
Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 5) = 1. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 10 start from, before any comparing?
Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 4) = 0. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 11 start from, before any comparing?
Answer: 3. Inside the box the answer is min(mirror radius, distance to the right edge): min(3, 3) = 3. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 12 start from, before any comparing?
Answer: 0. Inside the box the answer is min(mirror radius, distance to the right edge): min(0, 2) = 0. Copying more than the box reaches would assume characters nobody has looked at.
What radius does position 13 start from, before any comparing?
Answer: 1. Inside the box the answer is min(mirror radius, distance to the right edge): min(1, 1) = 1. Copying more than the box reaches would assume characters nobody has looked at.
How it runs, step by step
Find the longest palindrome in "abacabad". A palindrome can have an even or an odd length, and that is two cases nobody wants to write twice, so put a # in every gap and at both ends: "#a#b#a#c#a#b#a#d#". Every palindrome in there is now odd, centred on one position, and its radius is exactly the length of the palindrome in the original text.
Manacher over 17 transformed positions.
Position 1 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 1 is outside the box; starting radius 0.
Each comparison one step further out matches, 1 time, so the radius at 1 grows to 1, which is the palindrome "a" in the original text. It reaches further right than the old box, so the box moves to centre 1, right edge 2.
Radius at 1 is 1.
Position 2 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 2 is outside the box; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 2 stays 0.. The box is unchanged.
Radius at 2 is 0.
Position 3 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 3 is outside the box; starting radius 0.
Each comparison one step further out matches, 3 times, so the radius at 3 grows to 3, which is the palindrome "aba" in the original text. It reaches further right than the old box, so the box moves to centre 3, right edge 6.
Radius at 3 is 3.
Position 4 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.
Position 4 mirrors 2; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 4 stays 0.. The box is unchanged.
Radius at 4 is 0.
Position 5 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.
Position 5 mirrors 1; starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 5 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 5 is 1.
Position 6 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 6 is outside the box; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 6 stays 0.. The box is unchanged.
Radius at 6 is 0.
Position 7 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 7 is outside the box; starting radius 0.
Each comparison one step further out matches, 7 times, so the radius at 7 grows to 7, which is the palindrome "abacaba" in the original text. It reaches further right than the old box, so the box moves to centre 7, right edge 14.
Radius at 7 is 7.
Position 8 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 6, with radius 0. The mirror can be copied, but only as far as the box reaches: 6. So the starting radius is the smaller of the two, 0.
Position 8 mirrors 6; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 8 stays 0.. The box is unchanged.
Radius at 8 is 0.
Position 9 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 5, with radius 1. The mirror can be copied, but only as far as the box reaches: 5. So the starting radius is the smaller of the two, 1.
Position 9 mirrors 5; starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 9 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 9 is 1.
Position 10 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 4, with radius 0. The mirror can be copied, but only as far as the box reaches: 4. So the starting radius is the smaller of the two, 0.
Position 10 mirrors 4; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 10 stays 0.. The box is unchanged.
Radius at 10 is 0.
Position 11 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 3, with radius 3. The mirror can be copied, but only as far as the box reaches: 3. So the starting radius is the smaller of the two, 3.
Position 11 mirrors 3; starting radius 3.
Comparing the characters one step out fails immediately, so the radius at 11 stays 3., which is the palindrome "aba" in the original text. The box is unchanged.
Radius at 11 is 3.
Position 12 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.
Position 12 mirrors 2; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 12 stays 0.. The box is unchanged.
Radius at 12 is 0.
Position 13 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.
Position 13 mirrors 1; starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 13 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 13 is 1.
Position 14 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 14 is outside the box; starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 14 stays 0.. The box is unchanged.
Radius at 14 is 0.
Position 15 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 15 is outside the box; starting radius 0.
Each comparison one step further out matches, 1 time, so the radius at 15 grows to 1, which is the palindrome "d" in the original text. It reaches further right than the old box, so the box moves to centre 15, right edge 16.
Radius at 15 is 1.
The largest radius is 7 at position 7, which is the palindrome "abacaba" starting at index 0 of the original text. Every position was visited once and the right edge of the box only ever moves forward, so the 27 character comparisons are O(n) in total: the mirror is what turns the obvious O(n^2) expansion into linear time.
The longest palindrome is abacaba, length 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.