KMP Algorithm (Pattern Matching)

The problem with brute force

You want to find all places where pattern p (length m) appears inside text t (length n). Brute force: slide p over every position in t and compare. On a mismatch, shift by 1 and restart — O(n × m).

For n = 1 000 000 and m = 1 000, that is 1 billion character comparisons. Knuth, Morris, and Pratt found a way to do it in O(n + m) — by never going backwards in the text.

The reading comprehension story

Step 1 — Build the failure function

The failure function fail[i] stores the length of the longest proper prefix of p[0..i] that is also a suffix of p[0..i].

"Proper" means not the full string itself.

Pattern: "ABCABD"

i=0  p[0..0]="A"      prefixes: ""         → fail[0] = 0
i=1  p[0..1]="AB"     longest match: ""    → fail[1] = 0
i=2  p[0..2]="ABC"    longest match: ""    → fail[2] = 0
i=3  p[0..3]="ABCA"   longest match: "A"   → fail[3] = 1
i=4  p[0..4]="ABCAB"  longest match: "AB"  → fail[4] = 2
i=5  p[0..5]="ABCABD" longest match: ""    → fail[5] = 0

fail = [0, 0, 0, 1, 2, 0]

How to build it in O(m):

def build_failure(pattern: str) -> list[int]:
    m    = len(pattern)
    fail = [0] * m
    j    = 0               # length of current matching prefix

    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = fail[j - 1]    # fall back using previously computed values
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j

    return fail

Step 2 — Search the text

Using fail, search for all occurrences of pattern in text:

def kmp_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        return []

    fail    = build_failure(pattern)
    matches = []
    j       = 0               # number of pattern characters matched so far

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = fail[j - 1]   # mismatch: fall back in pattern, NOT in text

        if text[i] == pattern[j]:
            j += 1

        if j == m:            # full pattern matched
            matches.append(i - m + 1)
            j = fail[j - 1]   # prepare for next possible match

    return matches

The key invariant: i (the text pointer) never goes backward. Only j (the pattern pointer) falls back, and it falls back using precomputed fail values — O(1) per fall-back amortised.

Frame-by-frame: text = "ABCABCABD", pattern = "ABCABD"

fail = [0, 0, 0, 1, 2, 0]   (computed in Step 1)

i=0  t[0]='A', j=0: match → j=1
i=1  t[1]='B', j=1: match → j=2
i=2  t[2]='C', j=2: match → j=3
i=3  t[3]='A', j=3: match → j=4
i=4  t[4]='B', j=4: match → j=5
i=5  t[5]='C', j=5: mismatch (pattern[5]='D')
                  → j = fail[4] = 2
     t[5]='C', j=2: match → j=3
i=6  t[6]='A', j=3: match → j=4
i=7  t[7]='B', j=4: match → j=5
i=8  t[8]='D', j=5: match → j=6 == m → MATCH at position 8-6+1 = 3
                  → j = fail[5] = 0

Matches: [3]  ✅  (text[3..8] = "ABCABD")

Notice: at i=5, the mismatch sent j from 5 to 2 — we kept "ABC" progress from the previous window. The text pointer i never moved back.

Application: Repeated Substring Pattern (LC #459)

Does string s consist of a repeated substring? E.g. "abcabc" = "abc" repeated twice.

KMP trick: concatenate s + s, remove first and last character, check if s is a substring.

def repeatedSubstringPattern(s: str) -> bool:
    doubled = (s + s)[1:-1]    # remove first and last char
    return s in doubled        # Python's `in` uses KMP internally

Why does this work? If s has a repeating period p, then s + s contains a copy of s starting at position p (not 0 and not len(s)). Removing the first and last characters prevents the trivial match at position 0 and at the end.

The one idea to remember

Where to spot this pattern

Trigger words:

• "find all occurrences of pattern in text"
• "implement strStr()" or "needle in haystack"
• "repeated substring" — does it consist of a smaller repeated block?
• "shortest repeating period"

Distinguish from Rolling Hash (2.05): Both solve pattern matching in O(n). KMP has zero false positives (deterministic), Rolling Hash may need verification. For interviews, either is acceptable — KMP is more common for classic pattern matching; Rolling Hash is favoured for "find repeated/distinct substrings" problems.

Common traps

Complexity

# Phase 1: Build failure function — O(m)
fail = [0] * m;  j = 0
for i in range(1, m):
    while j > 0 and p[i] != p[j]: j = fail[j-1]
    if p[i] == p[j]: j += 1
    fail[i] = j

# Phase 2: Search — O(n)
j = 0
for i in range(n):
    while j > 0 and t[i] != p[j]: j = fail[j-1]
    if t[i] == p[j]: j += 1
    if j == m: record i-m+1; j = fail[j-1]

Check yourself

Practice problems

Next up: Z-Algorithm — a simpler alternative to KMP that computes the Z-array: the length of the longest substring starting at each position that matches a prefix of the string.