KMP algorithm — failure function, O(n+m) — full derivation

WHAT problem are we solving?

WHAT: Find all occurrences of a pattern $P$ (length $m$) inside a text $T$ (length $n$).

WHY naive is slow: Naive matching compares $P$ at every shift. On adversarial input like $T=\texttt{aaaa...a}$, $P=\texttt{aaa...ab}$ it does $O(nm)$ work, re-scanning the same text characters again and again.

HOW KMP wins: The text pointer $i$ only ever moves forward. When a mismatch happens at pattern position $j$, instead of resetting $j=0$, we set $j=\pi[j-1]$ — jumping the pattern to its longest reusable prefix. Each text char is "examined" $O(1)$ amortized times → $O(n+m)$.

The failure function $\pi$ (the whole trick)

Worked: build $\pi$ for ababaca

Why π[4]=3? ababa: prefix aba = suffix aba. Longer (abab) is not a suffix. So 3.

Why π[5]=0? ababac ends in c; no prefix of ababac ends in c except the whole thing (not proper). So 0.

DERIVING the $\pi$-computation algorithm from scratch

We build $\pi$ incrementally. Assume we know $\pi[0..i-1]$ and want $\pi[i]$. Let $j=\pi[i-1]$ = length of the best prefix-suffix for the previous position.

Case 1 — we can extend. If $S[i]=S[j]$, then the prefix S[0..j-1] that was a suffix can grow by one char on both ends. So $\pi[i]=j+1$.

Why this step? A border (prefix=suffix) of length $j$ for S[0..i-1], plus one matching char, gives a border of length $j+1$ for S[0..i].

Case 2 — mismatch, fall back. If $S[i]\ne S[j]$ and $j>0$, the next-best candidate border length is $\pi[j-1]$. We set $j\leftarrow\pi[j-1]$ and retry.

Why $\pi[j-1]$? The longest border shorter than $j$ that is also a border of the current prefix is exactly the longest border of that border — which is $\pi[j-1]$. This recursion walks down the chain of nested borders.

Case 3 — bottomed out. If $j=0$ and still mismatch, $\pi[i]=0$.

pi[0] = 0
for i = 1 .. m-1:
    j = pi[i-1]
    while j > 0 and S[i] != S[j]:
        j = pi[j-1]          # fall back along border chain
    if S[i] == S[j]:
        j += 1
    pi[i] = j

DERIVING the matching loop

Run the same machine over the text. Let $i$ index $T$, $j$ index $P$.

j = 0
for i = 0 .. n-1:
    while j > 0 and T[i] != P[j]:
        j = pi[j-1]           # mismatch → slide pattern, keep i
    if T[i] == P[j]:
        j += 1
    if j == m:                # full match ending at i
        report match at i-m+1
        j = pi[j-1]           # continue searching for overlapping matches

Why don't we move i back on mismatch? Because the prefix P[0..π[j-1]-1] is guaranteed equal to the text already scanned. Re-reading would re-confirm a known equality. So $i$ marches forward only.

WHY it is O(n+m) — the amortized proof

This is the key insight that separates KMP from naive: the amortized cost of the fallback is bounded by how much $j$ ever grew.

Full match example: $P=$abab, $T=$ababaababab

First $\pi$ for abab: [0,0,1,2].

Why report 0 then 6 then 7? Overlapping occurrences abab at indices 0, 6, 7. At i=5 the fallback from j=3 to 1 reused the matched a instead of restarting.

Active Recall

Connections

• Z-algorithm — alternative linear string matching via Z-array
• Rabin-Karp — hashing-based matching, expected $O(n+m)$
• Aho-Corasick — generalizes KMP failure links to many patterns (a trie of fail links)
• Suffix Automaton & Suffix Array — heavier structures for repeated queries
• Amortized Analysis — the potential argument used for the $O(n+m)$ bound
• Borders and Periods of Strings — $\pi[m-1]$ gives the smallest period of $P$

Concept Map

Hinglish (regional understanding)