How It Works

This chapter traces KMP, Rabin-Karp, tries and the Z-algorithm by hand on small inputs. Working out the tables yourself makes the code in the next chapter much easier to read.

KMP step 1: the prefix function (failure table)

The prefix function pi[i] is the length of the longest border of the first i + 1 characters of the pattern (p[0..i]). It is also called the failure function or failure table. Here it is for ababaca.

The computation runs left to right and carries k, the border length at the previous position.

1. i = 1: p[1] = b differs from p[0] = a and k = 0, so pi[1] = 0.
2. i = 2: p[2] = a equals p[0], so k = 1 and pi[2] = 1.
3. i = 3, 4: the characters keep matching and k grows to 2, then 3.
4. i = 5: p[5] = c differs from p[3] = b. Instead of starting over, fall back to a shorter border: k = pi[k - 1] = pi[2] = 1. p[1] = b still differs, so k = pi[0] = 0; p[0] = a differs too, and pi[5] = 0.
5. i = 6: p[6] = a equals p[0], so pi[6] = 1.

Step 4 is the key idea. On a mismatch you jump straight to the next shorter border inside the current one. Because a border of a border is itself a border, no candidate is skipped.

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi


print(prefix_function("ababaca"))  # [0, 0, 1, 2, 3, 0, 1]

KMP step 2: scanning the text

Searching works the same way. k is the number of pattern characters matched so far, and the text pointer i never moves backwards. Search for abab (pi = [0, 0, 1, 2]) in abababcabab:

Setting k = pi[m - 1] after a match, instead of 0, is what finds overlapping occurrences such as the ones at 0 and 2.

Rabin-Karp: the rolling hash

Rabin-Karp compares the hash of each length-m window with the hash of the pattern. When the window slides by one, the hash is not recomputed from scratch: the leading character is removed and the new one added in O(1).

h(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1]) mod M
next window: h' = ((h - s[i]·B^(m-1))·B + s[i+m]) mod M

To keep the numbers readable, use a digit string with B = 10 and M = 11. The text is 31415926, the pattern is 1592, and the pattern hash is 1592 mod 11 = 8.

As the last row shows, equal hashes do not guarantee equal strings, so a hash hit must always be confirmed by comparing characters. Real code uses a large prime modulus such as 10**9 + 7 and a random base to make collisions rare.

def window_hashes(text: str, m: int, base: int = 10, mod: int = 11) -> list[int]:
    high = pow(base, m - 1, mod)
    h = 0
    for ch in text[:m]:
        h = (h * base + int(ch)) % mod
    out = [h]
    for i in range(len(text) - m):
        h = ((h - int(text[i]) * high) * base + int(text[i + m])) % mod
        out.append(h)
    return out


print(window_hashes("31415926", 4))  # [6, 7, 1, 8, 8]

Tries: a tree of shared prefixes

A trie is a tree you walk down one character at a time. After inserting car, cart, cat and dog, the common prefix ca is stored once. A * marks a node where a word ends.

(root)
 ├─ c ─ a ─ r* ─ t*
 │        └─ t*
 └─ d ─ o ─ g*

To autocomplete ca, walk down c then a and collect every end-of-word mark below that node: car, cart, cat. The walk costs time proportional to the prefix length, independent of how many words the dictionary holds.

The Z-algorithm in brief

In the Z-array, z[i] is the length of the longest common prefix of s[i:] and s. For aabxaab it is [7, 1, 0, 0, 3, 1, 0] (by convention z[0] is the length or 0). To search, build the Z-array of pattern + "$" + text and report positions where the value equals m; the separator $ must not appear in either string. By reusing the rightmost interval [l, r) already matched (the Z-box), the whole array is computed in O(n + m).

Summary

• On a mismatch the prefix function falls back to a border of a border, so the text pointer never moves back.
• After a match KMP sets k = pi[m - 1], which also finds overlapping occurrences.
• Rabin-Karp updates each window hash in O(1) and confirms hash hits character by character to reject false positives.
• Tries share common prefixes; the Z-array solves the same problems as KMP from a different angle.