String Algorithms: KMP, Z, and Rabin-Karp

Naively checking "does pattern occur starting at every index of text" costs $O(n \cdot m)$ -- for every one of the n starting positions, you might compare up to m characters before finding a mismatch. All three algorithms in this lesson bring that down to linear time, $O(n + m)$, by reusing information about the pattern (or the text) instead of re-comparing from scratch after every mismatch.

What you'll learn

• KMP's failure function -- a precomputed array that tells the search exactly how far to fall back after a mismatch, so the text pointer never moves backward.
• The Z-algorithm -- for every position, how long a prefix of the string is repeated starting there; a single array that answers pattern matching, string periodicity, and more.
• Rabin-Karp -- comparing a rolling hash of each window instead of the characters themselves, with a verification step to rule out hash collisions.
• Which of the three to reach for, based on the problem shape.

The cue

When it is the wrong tool. If the alphabet is tiny and the answer only needs counts of characters, a sliding window with a frequency map is simpler and faster -- LC 438 (find all anagrams) is a window problem, not a KMP problem, even though it sounds like matching. If you need every substring of a set queried repeatedly, a trie or suffix automaton is the right structure. And if n is under a few thousand, Python's built-in str.find -- C-speed $O(nm)$ worst case, near-linear in practice -- beats a hand-written KMP on wall clock. Reach for these when the constraint forces you to, or when the failure function itself is the answer.

KMP: the failure function fixes "never move backward"

A naive search that mismatches at text position i and pattern position k restarts the pattern from 0 -- but it re-checks characters that are guaranteed to match, because they matched the first time around. KMP's failure function (also called the prefix function) precomputes, for every prefix of the pattern, the length of the longest proper prefix that is also a suffix of it. That length is exactly how far the pattern pointer should fall back on a mismatch -- no re-scanning the text needed.

def build_failure(pattern):
    m = len(pattern)
    fail = [0] * m
    k = 0                                  # length of the current matching prefix/suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = fail[k - 1]                 # fall back to the next-best prefix length
        if pattern[i] == pattern[k]:
            k += 1
        fail[i] = k
    return fail
 
 
def kmp_search(text, pattern):
    if not pattern:
        return []
    fail = build_failure(pattern)
    matches = []
    k = 0                                   # how many pattern characters matched so far
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = fail[k - 1]                 # the same fallback trick, applied to the text scan
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            matches.append(i - k + 1)       # full match ends here -- record its start
            k = fail[k - 1]                 # keep scanning for overlapping matches
 
    return matches
 
 
pattern = "abc"
text = "ababcababcabc"
print("failure function of 'ababc':", build_failure("ababc"))
print("matches of 'abc' in text:", kmp_search(text, pattern))

  graph LR
    N0(("0")) -- "a" --> N1(("1"))
    N1 -- "b" --> N2(("2"))
    N2 -- "a" --> N3(("3"))
    N3 -- "b" --> N4(("4"))
    N4 -- "c" --> N5(("5 match"))
    N2 -.->|"mismatch: fail = 0"| N0
    N3 -.->|"mismatch: fail = 1"| N1
    N4 -.->|"mismatch: fail = 2"| N2

Each solid state is "this many characters of the pattern matched so far." On a mismatch, instead of resetting all the way to state 0, the dashed edge jumps to the failure value -- the longest prefix of "ababc" that is also a suffix of what's matched so far. That's the entire speedup: the automaton never revisits a text character twice.

Visual intuition

The prefix function is the whole of KMP; the search loop is a re-run of the same idea against the text. Watch the fallback — k = pi[k-1] — because that single line is why the scan never rewinds:

1def prefix_function(s):2    pi = [0] * len(s)3    k = 0                          # length of the current border4    for i in range(1, len(s)):5        while k and s[i] != s[k]:6            k = pi[k - 1]          # fall back, never restart at 07        if s[i] == s[k]:8            k += 19        pi[i] = k10    return pi

The Z-algorithm: how far does the prefix repeat here?

The Z-array answers a single question for every index i of a string s: what's the length of the longest substring starting at i that matches a prefix of s? z[0] is conventionally the whole string's length (or left undefined) since it's a trivial match with itself.

def z_array(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 0                              # the rightmost Z-box found so far: s[l:r] == s[0:r-l]
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])       # reuse work already done inside the current Z-box
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                         # extend the match past what the Z-box guaranteed
        if i + z[i] > r:
            l, r = i, i + z[i]                # this match extends further right -- update the box
    return z
 
 
def z_search(text, pattern):
    combined = pattern + "#" + text           # "#" can't appear in either string -- a safe separator
    z = z_array(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
 
 
print("Z-array of 'aabxaab':", z_array("aabxaab"))
print("matches of 'ab' via Z:", z_search("abcabcabab", "ab"))

The pattern-search trick: glue pattern + "#" + text together and compute one Z-array over the whole thing. Any position in the text part whose Z-value equals len(pattern) means the pattern matches starting there -- because "the prefix repeats for exactly len(pattern) characters" is "the pattern occurs here."

Rabin-Karp: compare hashes, not characters

Instead of comparing characters directly, Rabin-Karp hashes each m-length window of the text and compares that hash against the pattern's hash. The key trick is a rolling hash: sliding the window one position right updates the hash in $O(1)$ by removing the outgoing character's contribution and adding the incoming one, instead of rehashing the whole window.

def rabin_karp(text, pattern, base=256, mod=10**9 + 7):
    n, m = len(text), len(pattern)
    if m > n:
        return []
 
    high_order = pow(base, m - 1, mod)        # value of the leading digit's place, mod `mod`
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod
 
    matches = []
    for i in range(n - m + 1):
        if window_hash == pattern_hash and text[i:i + m] == pattern:
            matches.append(i)                 # hashes agree AND the substring itself checks out
        if i < n - m:
            window_hash = (
                (window_hash - ord(text[i]) * high_order) * base + ord(text[i + m])
            ) % mod                            # slide the window one character to the right
 
    return matches
 
 
print(rabin_karp("abracadabra", "abra"))   # expect [0, 7]

Dry run

The failure function of ababcabab

k is the length of the border matched so far. The only interesting row is the one where the while fires.

Final: fail = [0, 0, 1, 2, 0, 1, 2, 3, 4].

Row 4 is the algorithm. k was 2, meaning ab was matched; s[4] is c and s[2] is a, so they disagree. The fallback asks fail[1], which is 0 -- there is no shorter border of ab to retry -- so k drops straight to 0. Contrast with a pattern like aabaaab, whose failure array is [0, 1, 0, 1, 2, 2, 3]: at i = 5 the border shrinks from 2 to 1 and then immediately regrows to 2, because s[5] does match s[1]. That partial retry -- landing on a shorter border instead of restarting -- is exactly the work KMP saves over a naive restart.

The last value, fail[8] = 4, says the longest proper border of ababcabab is abab -- length 4. That single number is the answer to LC 1392 (longest happy prefix). The search is optional; often the array is the problem.

Searching with overlaps

text = "aabaabaaa", pattern = "aabaa", fail = [0, 1, 0, 1, 2]. Note the pattern overlaps itself, which is what makes this trace worth reading.

Matches at [0, 3] -- and they overlap, sharing text[3:5] == "aa". That is why the post-match line is k = fail[k - 1] and not k = 0. Resetting to 0 would throw away the two characters already matched at the tail and miss the occurrence starting at 3 entirely. If a problem wants non-overlapping occurrences, k = 0 is the correct change -- and knowing which line to touch is the point.

Nine text characters, nine iterations, exactly one fallback in the whole scan. i only ever advances and each fallback strictly decreases k, and k only grows by one per step -- so total fallbacks are bounded by total increments. That is the linear-time argument, and it is invisible in the code.

The Z-array reusing a Z-box

s = "aabxaab". The box [l, r) is the rightmost prefix-match found so far.

Z = [7, 1, 0, 0, 3, 1, 0].

Rows 5 and 6 are the entire optimisation. i = 4 did three character comparisons and established a box covering positions 4 through 6. Positions 5 and 6 fall inside that box, so their answers are copied from z[i - l] -- z[1] = 1 and z[2] = 0 -- with zero character comparisons. The string inside a Z-box is by definition equal to the prefix, so work done at the prefix is already work done here.

The min(r - i, z[i - l]) matters: without the min, a copied value could run past the box's right edge into territory that was never verified. The while then extends past the guarantee when it can, and only a successful extension moves the box.

Pattern search by concatenation

z_search("abcabcabab", "ab") builds "ab#abcabcabab" and reads one array:

index    0  1  2  3  4  5  6  7  8  9 10 11 12
char     a  b  #  a  b  c  a  b  c  a  b  a  b
z       13  0  0  2  0  0  2  0  0  2  0  2  0

Every index past the separator with z[i] == 2 is a match: indices 3, 6, 9, 11, which map back to text positions 0, 3, 6, 8. The separator earns its keep -- it must be a character appearing in neither string, or a Z-value could run from the pattern straight into the text and overcount.

Rabin-Karp, and why the verification line is not optional

With a real modulus ($10^9 + 7$) on "abracadabra" searching "abra", exactly two windows hash to 633841754 and both are genuine matches at 0 and 7. Now shrink the modulus to 101 and search "abccabra":

Without the text[i:i+m] == pattern check the function returns [0, 4]. With it, [4]. A small modulus makes this easy to demonstrate, but the failure mode is identical at $10^9 + 7$ -- it just takes an adversarial input rather than an eight-character one. The comparison is what converts "probably" into "definitely", and it costs nothing amortised because it only runs when the hashes already agree.

Complexity

Three points worth being precise about:

• KMP's linearity is amortised, not per-step. One text character can trigger several fallbacks. The bound comes from the potential argument: k rises by at most 1 per character and every fallback strictly lowers it, so total fallbacks across the scan are at most n. Say "each character is examined a constant number of times on average"; that is what the trace above shows with one fallback in nine steps.
• Rabin-Karp's $O(n)$ is expected, not worst case. With an adversarially chosen input and a fixed base and modulus, every window can collide and each triggers an $O(m)$ verification -- $O(nm)$. The defences are a large prime modulus, a randomised base chosen at run time, or double hashing with two independent moduli. Competitive-programming judges do hack fixed hashes.
• Space is where they differ most. KMP needs $O(m)$ for the pattern only, which matters when the text is streamed and never fully held. The Z-algorithm needs $O(n + m)$ because the concatenation is materialised. Rabin-Karp needs $O(1)$ -- one integer -- which is why it is the one that scales to 2D grids and to sets of patterns.

Which one to use

The variant map

Practice -- real LeetCode problems

All three are the prefix function -- KMP's failure table -- in three disguises. Write it once here and you own the family: substring search, longest border, and the palindrome trick.

LC 28 -- Find the Index of the First Occurrence in a String · Easy

Problem. Return the index of the first occurrence of needle in haystack, or -1 if it is not present.

Constraints. 1 <= len(haystack), len(needle) <= 10**4, lowercase letters.

Examples. "sadbutsad", "sad" gives 0 · "leetcode", "leeto" gives -1 · "mississippi", "issip" gives 4

Press Run to see what your code prints.

LC 1392 -- Longest Happy Prefix · Hard

Problem. A happy prefix is a non-empty prefix that is also a suffix, excluding the whole string itself. Return the longest happy prefix of s, or "" if there is none.

Constraints. 1 <= len(s) <= 10**5, lowercase letters.

Examples. "level" gives "l" · "ababab" gives "abab" · "a" gives ""

Press Run to see what your code prints.

LC 214 -- Shortest Palindrome · Hard

Problem. You may add characters only in front of s. Return the shortest palindrome you can make this way.

Constraints. 0 <= len(s) <= 5 * 10**4, lowercase letters.

Examples. "aacecaaa" gives "aaacecaaa" · "abcd" gives "dcbabcd" · "" gives ""

Press Run to see what your code prints.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

Interview follow-ups

Self-check

Recall card

• All three replace $O(nm)$ with $O(n + m)$ by never re-examining a text character after a mismatch.
• fail[i] = longest proper prefix of s[0..i] that is also a suffix. Property of the pattern only. fail[m - 1] alone answers longest-happy-prefix.
• The fallback is k = fail[k - 1], both when building the array and when scanning.
• Linearity is amortised: k rises by at most 1 per character, every fallback lowers it, so fallbacks total at most n. That sentence is the proof.
• After a match, k = fail[k - 1] finds overlaps; k = 0 does not. Decide which the problem wants.
• Period = n - fail[n - 1], and it tiles only if n % period == 0. The divisibility check is the whole of LC 459.
• z[i] = longest prefix of s starting at i. Reuse inside the Z-box via min(r - i, z[i - l]) -- the min is what keeps the copy inside verified territory.
• Z search needs a separator absent from both strings, or matches leak across the join.
• Rabin-Karp is expected linear, worst case $O(nm)$. Always verify a hash hit with a real comparison; randomise the base against hacking.
• Pick by shape: borders and periods -> KMP · prefix overlap everywhere -> Z · many patterns, substring equality, 2D, or $O(1)$ space -> rolling hash. Streamed text -> KMP, the only one that never needs the text in memory.

Recap

• KMP: precompute the failure function (longest prefix-that's-also-a- suffix for every prefix), then never move the text pointer backward during the search. $O(n + m)$.
• Z-algorithm: z[i] is how far the prefix repeats starting at i; glue pattern + "#" + text and look for z[i] == len(pattern). Also the go-to for periodicity and border questions. $O(n + m)$.
• Rabin-Karp: roll a hash across the text in $O(1)$ per step, but always verify a hash match with a real substring comparison to rule out collisions.
• Reach for KMP or Z when you need a hard linear-time guarantee on a single pattern; reach for Rabin-Karp when you're matching many patterns at once or need cheap substring-equality checks.

Next: Bit Manipulation Tricks -- the low-level operations (masks, shifts, XOR) that power bitmask DP, subset enumeration, and a whole class of O(1)-space interview and CP problems.