AlgoScope

String Matching

algorithmintermediateTime O(n + m)Space O(m)

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.

txtpatacabbcabcaabcaabca

Boyer-Moore compares the pattern from its right end. On a mismatch it looks at the text character that failed, the bad character, and slides the pattern so that its rightmost copy of that character lines up with it; a character not in the pattern at all lets the whole pattern jump past. The last table is precomputed: a:3 b:1 c:2.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.

  1. Mismatch on text 'b' at offset 3; its last index in the pattern is 1. How far does the pattern slide?

    • 2
    • 1
    • 4

    Answer: 2. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  2. Mismatch on text 'c' at offset 3; its last index in the pattern is 2. How far does the pattern slide?

    • 1
    • 4

    Answer: 1. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  3. Mismatch on text 'b' at offset 0; its last index in the pattern is 1. How far does the pattern slide?

    • 1
    • 4

    Answer: 1. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  4. Mismatch on text 'b' at offset 3; its last index in the pattern is 1. How far does the pattern slide?

    • 2
    • 1
    • 4

    Answer: 2. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  5. Every character matched at shift 6. How far does the pattern slide?

    • 1
    • 4
    • 0

    Answer: 1. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  6. Mismatch on text 'a' at offset 2; its last index in the pattern is 3. How far does the pattern slide?

    • 1
    • 4
    • 3

    Answer: 1. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  7. Mismatch on text 'b' at offset 3; its last index in the pattern is 1. How far does the pattern slide?

    • 2
    • 1
    • 4

    Answer: 2. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

  8. Every character matched at shift 10. How far does the pattern slide?

    • 1
    • 4
    • 0

    Answer: 1. Slide by max(1, j - last[bad]); a match or a backwards slide means 1.

How it runs, step by step

  1. Boyer-Moore compares the pattern from its right end. On a mismatch it looks at the text character that failed, the bad character, and slides the pattern so that its rightmost copy of that character lines up with it; a character not in the pattern at all lets the whole pattern jump past. The last table is precomputed: a:3 b:1 c:2.

    Boyer-Moore with last occurrence table a:3 b:1 c:2.

  2. Shift 0: compare from the right. 0 agree, then text 'b' at offset 3 differs from 'a'. The rightmost 'b' in the pattern is at index 1, so slide 3 - 1 = 2 to line them up.

    Bad character b, slide 2.

  3. Shift 2: compare from the right. 0 agree, then text 'c' at offset 3 differs from 'a'. The rightmost 'c' in the pattern is at index 2, so slide 3 - 2 = 1 to line them up.

    Bad character c, slide 1.

  4. Shift 3: compare from the right. 3 agree, then text 'b' at offset 0 differs from 'a'. The rightmost 'b' in the pattern is to the right of the mismatch, which would slide backwards, so slide by 1.

    Bad character b, slide 1.

  5. Shift 4: compare from the right. 0 agree, then text 'b' at offset 3 differs from 'a'. The rightmost 'b' in the pattern is at index 1, so slide 3 - 1 = 2 to line them up.

    Bad character b, slide 2.

  6. Shift 6: compare from the right. All 4 characters agree, a match at index 6. Slide by 1.

    Match at index 6.

  7. Shift 7: compare from the right. 1 agree, then text 'a' at offset 2 differs from 'c'. The rightmost 'a' in the pattern is to the right of the mismatch, which would slide backwards, so slide by 1.

    Bad character a, slide 1.

  8. Shift 8: compare from the right. 0 agree, then text 'b' at offset 3 differs from 'a'. The rightmost 'b' in the pattern is at index 1, so slide 3 - 1 = 2 to line them up.

    Bad character b, slide 2.

  9. Shift 10: compare from the right. All 4 characters agree, a match at index 10. Slide by 1.

    Match at index 10.

  10. Found at 6, 10. 8 alignments and 18 character comparisons, against 11 alignments for the naive scan. With a large alphabet most text characters are absent from the pattern and the pattern jumps its whole length, sublinear on average; the full algorithm adds a good suffix rule for the worst case.

    Matches at 6, 10.

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;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

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

Next up