String Algorithms: KMP, Z, and Rabin-Karp

Naively checking “does patternpattern occur starting at every index of texttext” costs $O(n \cdot m)$ — for every one of the nn starting positions, you might compare up to mm 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.

KMP: the failure function fixes “never move backward”

A naive search that mismatches at text position ii and pattern position kk restarts the pattern from 00 — 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.

kmp_failure_and_search.py

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))

kmp_failure_and_search.py

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))

diagram KMP automaton for pattern 'ababc' -- solid edges match, dashed edges are the failure-function fallback mermaid

  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 00, the dashed edge jumps to the failure value — the longest prefix of "ababc""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.

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

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

z_algorithm.py

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"))

z_algorithm.py

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 + "#" + textpattern + "#" + text together and compute one Z-array over the whole thing. Any position in the texttext part whose Z-value equals len(pattern)len(pattern) means the pattern matches starting there — because “the prefix repeats for exactly len(pattern)len(pattern) characters” is “the pattern occurs here.”

Rabin-Karp: compare hashes, not characters

Instead of comparing characters directly, Rabin-Karp hashes each mm-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.

rabin_karp.py

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]

rabin_karp.py

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]

Which one to use

Algorithm	Time	Space	Best for
KMP	$O(n + m)$	$O(m)$	Single-pattern search where you want a hard guarantee of no backtracking; the failure function itself is often the real answer (periods, borders).
Z-algorithm	$O(n + m)$	$O(n + m)$	Prefix-overlap questions — pattern search via concatenation, shortest palindrome/period, longest happy prefix.
Rabin-Karp	$O(n + m)$ average, $O(n \cdot m)$ worst case	$O(1)$	Multiple-pattern search (hash every pattern once into a set), 2D grid or substring-equality checks, anagram-window problems.

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 needleneedle in haystackhaystack, or -1-1 if it is not present.

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

Examples. "sadbutsad""sadbutsad", "sad""sad" gives 00 · "leetcode""leetcode", "leeto""leeto" gives -1-1 · "mississippi""mississippi", "issip""issip" gives 44

Editorial · approach, complexity, follow-ups

pi[i]pi[i] is the length of the longest proper prefix of pattern[:i+1]pattern[:i+1] that is also a suffix of it — its longest border. On a mismatch you jump k = pi[k-1]k = pi[k-1], which is the next-longest border and therefore the next plausible alignment. The outer index ii never decreases, and that is the entire reason KMP is $O(n + m)$ where the naive double loop is $O(nm)$ .

The concatenation trick — searching for needleneedle by building the prefix function of needle + sentinel + haystackneedle + sentinel + haystack — means you only ever have to remember one routine. Any pipi value reaching len(needle)len(needle) is a full occurrence.

Time $O(n + m)$ . Space $O(n + m)$ .

The sentinel is mandatory. Without it a “match” could straddle the boundary, half in the needle and half in the haystack. It must be a character that cannot appear in either — "\x00""\x00" here, or "#""#" when the alphabet is known to be letters.
The index arithmetic. The match ends at position ii in the concatenation, and before the haystack sit len(needle)len(needle) characters plus one sentinel. Working through "a""a", "a""a" — where the answer must be 0 — is the fastest way to convince yourself of i - 2 * len(needle)i - 2 * len(needle).
A needle longer than the haystack returns -1-1 naturally, since pipi can never reach len(needle)len(needle). "aaa""aaa", "aaaa""aaaa" checks it.
while k and ...while k and ... then ifif, not elifelif. After the fallback loop you must still test the character at the new kk.
In real code you would write haystack.find(needle)haystack.find(needle). Say so, then show the algorithm — the problem exists to test the algorithm.

Follow-ups you should expect: “All occurrences, not just the first?” — collect every ii where pi[i]pi[i] hits len(needle)len(needle). “Rabin-Karp instead?” — rolling hash with a verification step on a hash hit; $O(n + m)$ expected, $O(nm)$ worst case, and the trade-off worth articulating. “Many needles at once?” — Aho-Corasick, which is KMP generalised to a trie. “The Z-algorithm?” — an equivalent linear method on the same concatenation, often easier to reason about. “Why not use a suffix automaton?” — overkill unless the haystack is fixed and queried many times.

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 ss, or """" if there is none.

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

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

Editorial · approach, complexity, follow-ups

The problem is the prefix function’s definition restated, so it is the cleanest possible drill on it. The value of doing it is that afterwards you will recognise “prefix that is also a suffix” instantly, in problems that hide it much better.

Time $O(n)$ . Space $O(n)$ .

Proper is automatic. pi[i]pi[i] never equals i + 1i + 1, because the fallback loop only ever compares a prefix against a shorter suffix. So "aaaa""aaaa" gives "aaa""aaa", not "aaaa""aaaa", with no explicit guard.
"abcd""abcd" gives """" — no border at all, and s[:0]s[:0] is the empty string, which is exactly what the problem wants returned.
"a""a" gives """". A single character has no proper non-empty border, and pi[-1]pi[-1] is 0.
"ababab""ababab" gives "abab""abab", length 4 — borders may overlap themselves. If you expected "ab""ab" you are thinking of non-overlapping repetitions, which is a different question.
Hashing would also work — compare prefix and suffix hashes for each length — but it is $O(n)$ with a collision risk and no simpler. Mention it and move on.

Follow-ups you should expect: “All borders, not just the longest?” — follow the chain pi[-1]pi[-1], pi[pi[-1]-1]pi[pi[-1]-1], and so on; that chain is the complete set of borders. “Is the string a repetition of a shorter block (LC 459)?” — yes exactly when n % (n - pi[-1]) == 0n % (n - pi[-1]) == 0 and pi[-1] > 0pi[-1] > 0; n - pi[-1]n - pi[-1] is the smallest period. “Shortest string with ss as both a prefix and a suffix, longer than ss?” — add n - pi[-1]n - pi[-1] characters. “Longest palindromic prefix?” — the next problem.

LC 214 — Shortest Palindrome · Hard

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

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

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

Editorial · approach, complexity, follow-ups

Two steps, and the first is the real content.

Step 1: what do we actually need? You may only prepend, so the tail of ss is fixed at the end of the result. To make a palindrome with the fewest additions, you want the longest palindromic prefix of ss; everything after it must be mirrored in front. If s = "aacecaaa"s = "aacecaaa", the longest palindromic prefix is "aacecaa""aacecaa" (length 7), leaving "a""a", so one "a""a" goes in front.

Step 2: find it with the prefix function. A prefix of ss that is also a suffix of ss reversed is a string that reads the same forwards and backwards — a palindromic prefix. So build pipi over s + sentinel + reverse(s)s + sentinel + reverse(s) and read the last value. The sentinel caps the value at len(s)len(s), preventing the degenerate match of ss against itself.

Time $O(n)$ . Space $O(n)$ .

The sentinel is what stops overshooting. Without it, "aaaa""aaaa" would report an overlap longer than the string and produce nonsense.
s[overlap:][::-1] + ss[overlap:][::-1] + s, not s[::-1] + ss[::-1] + s. Reversing the whole string always yields a palindrome, just not the shortest.
The empty string returns """", guarded explicitly because pi[-1]pi[-1] would index an empty list.
An already-palindromic ss has overlap == len(s)overlap == len(s), so nothing is prepended — "a""a" returns "a""a".
"aabba""aabba" gives "abbaabba""abbaabba". The longest palindromic prefix is "aa""aa", so "bba""bba" gets mirrored to "abb""abb" in front. Working this one by hand is the best check that you have the right prefix rather than the longest palindromic substring.

Follow-ups you should expect: “Prove that the longest palindromic prefix is the right target?” — any palindrome formed by prepending has ss as its suffix, so its prefix of length len(s)len(s) must be reverse(s)reverse(s)-compatible; minimising additions is maximising the overlap. “Append instead of prepend?” — longest palindromic suffix; reverse everything. “Both ends allowed?” — a different and easier problem. “Longest palindromic substring?” — not this at all; that is expand-around- centre or Manacher. “With hashing?” — test each prefix length with a rolling hash in both directions, $O(n)$ with a collision risk. “Manacher’s algorithm?” — also finds the longest palindromic prefix in $O(n)$ , and is the answer if the interviewer bans the concatenation trick.

LeetCode problem set

#	Problem	Difficulty	The twist
28	Find the Index of the First Occurrence in a String	Easy	KMP or the Z-algorithm search, applied directly: find the first occurrence of a pattern in a text
686	Repeated String Match	Medium	How many times must `aa` repeat before `bb` could occur inside it; KMP search on the repeated string after a bound on the repeat count
214	Shortest Palindrome	Hard	Find the longest palindromic prefix using KMP’s failure function on `s + "#" + reverse(s)s + "#" + reverse(s)`
1392	Longest Happy Prefix	Hard	Literally `build_failure(s)[-1]build_failure(s)[-1]` characters of `ss`: the failure function is the answer
438	Find All Anagrams in a String	Medium	Not a KMP/Z problem directly, but the same “slide a fixed-size window and compare in O(1)” spirit as Rabin-Karp, using a character-count fingerprint instead of a hash

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]z[i] is how far the prefix repeats starting at ii; glue pattern + "#" + textpattern + "#" + text and look for z[i] == len(pattern)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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

String Algorithms: KMP, Z, and Rabin-Karp

What you’ll learn

KMP: the failure function fixes “never move backward”

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

Rabin-Karp: compare hashes, not characters

Which one to use

Practice — real LeetCode problems

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

LC 1392 — Longest Happy Prefix · Hard

LC 214 — Shortest Palindrome · Hard

LeetCode problem set

Recap

Was this page helpful?