String matching: never start over

You search a long report for a word, and every place it occurs lights up; biologists look for short sequences in a genome of three billion letters. The job: find every position where a pattern of m letters occurs in a text of n letters.

The obvious way lines the pattern up under the text and compares letter by letter until one differs, then moves the pattern one place right and starts again. On ordinary text a mismatch usually comes at once. But search a million a's for “aaaab”, and at almost every position four letters match before one fails: about five million comparisons, and O(n·m) in the worst case, because every fresh start reads again letters already seen.

This lesson shows two ways not to start over. KMP (Knuth, Morris and Pratt) uses what it has already read, so it never moves back in the text. Rabin–Karp compares one number per window, a hash, instead of m letters.

text and pattern

The text T has n letters and the pattern P has m. P occurs at position s when T[s..s + m − 1] equals P. Two occurrences may overlap.

shift

Where the pattern sits under the text. The naive search tries every shift from 0 to n − m.

border

A string that is both a proper prefix and a suffix of another, where proper means shorter than the whole. “ab” is a border of “abcab”.

lps table

lps[i] is the length of the longest border of P[0..i], the pattern's first i + 1 letters: its longest proper prefix that is also a suffix. Also called the failure function.

rolling hash

A window's hash, updated rather than worked out again as the window slides: the leaving letter's share comes out and the entering letter's goes in.

Take the text “abcabcabd” and the pattern “abcabd”. At shift 0 the naive search matches a, b, c, a and b, then T[5] = 'c' fails against 'd'. It moves the pattern to shift 1 and compares T[1] with P[0], going back four letters in the text.

It doesn't need to. Those five text letters are known: they are “abcab”, the pattern's own start. A match at shift 1 would need “bcab” to begin the pattern, and one at shift 2 would need “cab” to; neither does. At shift 3 the last two matched letters, “ab”, are the pattern's first two. So the pattern can slide 3 places with “ab” already lined up, and compare T[5] with P[2] next.

That depends only on the pattern: “ab” is the longest border of “abcab”. So KMP first works out the longest border of every prefix of the pattern, the lps table. For “abcabd” it is 0, 0, 0, 1, 2, 0; lps[4] = 2 is the “ab”.

The table pays for itself on the naive search's worst case: a run of one letter, and a pattern ending in another.

Now the pattern is “aaa” and the text “aaaabaaa”. The run builds the table first, with two questions, then asks at every comparison of the search. Once two letters have matched, the choices also offer the naive restart, which KMP never makes. After each match, watch how far the pattern moves.

The table is built with the same move, run on the pattern against itself. border is the length of the border found so far, and the next pair to compare is P[i] and P[border]. If they match, lps[i] = border + 1 and i moves on. If not, fall back to the next-longest border, lps[border − 1], and try again; only when no border is left is lps[i] = 0. Each comparison moves i on or shrinks the border, and the border, growing at most one per step of i, can't shrink more than m times: under 2m comparisons, O(m). Here it is for “aabaaab”.

def build_lps(p):
    lps = [0] * len(p)
    border = 0
    i = 1
    while i < len(p):
        if p[i] == p[border]:
            border += 1
            lps[i] = border
            i += 1
        elif border > 0:
            border = lps[border - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

lps_table = build_lps('aabaaab')
print(*lps_table)

The search falls back the same way, j becoming lps[j − 1] after a mismatch, and that step is easy to get wrong.

Rabin–Karp takes a different shortcut: it compares each window's hash with the pattern's. Equal words always get equal hashes, so a window with a different hash is skipped unread. The visualiser's hash is like the one in the hash tables lesson, with smaller numbers: letters are digits from a = 1 to z = 26, read in base 26, keeping the remainder mod 101. For “car” that is (3 × 26² + 1 × 26 + 18) mod 101 = 52.

Hashing each window from scratch would cost m steps. So the hash rolls, like a sliding window's running total: take out the leaving letter's share (its value × $26^{m-1}$), multiply the rest by 26, and add the entering letter, a few steps whatever m is.

So Rabin–Karp is expected O(n + m), not guaranteed: each hit costs up to m letter comparisons, and a weak hash, or aaaa…a searched for aaa, makes nearly every window a hit: O(n·m). Its strength is many patterns of one length at once: keep their hashes in a hash set and look up each window's hash, in one pass.

A third linear method, the Z-algorithm, joins the pattern, a separator and the text into one string and measures, at every position, how far the letters agree with its start; where that reaches m, the pattern starts. Like KMP it reuses earlier comparisons, so it is O(n + m) too.

• The naive search restarts after every mismatch and reads the text again: O(n·m) on text like aaaa…ab.
• A border is a proper prefix that is also a suffix; its two copies may overlap. lps[i] is the length of the longest border of P[0..i], built by extending a border or falling back to a shorter one, in O(m).
• After a mismatch with j letters matched, KMP sets j = lps[j − 1] and compares the same text letter again. The text pointer never moves back: O(n + m) in all.
• Rabin–Karp rolls a window's hash in O(1) and compares letters only on a hit. Hits can be spurious, so the check stays: expected O(n + m), O(n·m) at worst.
• Next: palindromes, where Manacher's algorithm reuses mirror images as KMP reuses borders (its visualiser), and tries, for many words at once. Practise with Longest Palindromic Substring and Build a Prefix Tree, or try your own text on the KMP, Rabin–Karp and Z-algorithm visualisers.