KMP Pattern Matching

Why Naive Matching Gets Stuck

Suppose you are searching for the pattern ababaca inside a long log file. The obvious algorithm aligns the pattern under the text, compares character by character, and when a mismatch happens it slides the pattern one step to the right and starts the comparison from the beginning again. That feels harmless on short strings, but it can waste an astonishing amount of work because the algorithm forgets information it already proved.

The waste appears when the pattern contains self-overlap. If you have already matched ababa and then the next text character disagrees with pattern position 5, you should not need to re-check that the text suffix aba is still aba. Naive matching does exactly that. In the worst case, it compares almost the same characters over and over, so a text of length n and pattern of length m can cost O(nm) time.

text    = ababaababaca
pattern = ababaca

naive trace near the first mismatch:
- match a b a b a
- mismatch: text has 'a', pattern expects 'c'
- shift pattern by one
- compare many of the same a/b/a/b characters again

What the Prefix Function Means

KMP preprocesses the pattern into an array often called lps (longest proper prefix which is also a suffix), pi, or the failure function. For each position i, lps[i] tells you the length of the longest prefix of the pattern that also appears as a suffix ending at i. The word proper matters: the whole substring is not allowed to count as its own prefix.

That definition sounds abstract until you translate it into the search story. If you have matched pattern characters 0..i and then fail on the next character, lps[i] tells you how many matched characters are still useful. Those characters describe the largest prefix that is already sitting at the end of the text segment you just consumed, so they do not need to be matched again.

Building the LPS Array

Take the pattern ababaca. We build lps from left to right. Position 0 is always 0 because a one-character string has no proper prefix. After that, keep a variable length for the current border size. If the next pattern character matches pattern[length], the border extends by one. If it mismatches, do not drop straight to zero. First ask whether the current border has a smaller border of its own. That is exactly what earlier LPS values tell you.

index:   0 1 2 3 4 5 6
char:    a b a b a c a
lps:     0 0 1 2 3 0 1

key moment at index 5 ('c'):
- current border length = 3, meaning 'aba'
- compare pattern[5] = 'c' with pattern[3] = 'b' => mismatch
- fall back to lps[2] = 1
- compare pattern[5] = 'c' with pattern[1] = 'b' => mismatch
- fall back to lps[0] = 0
- compare pattern[5] = 'c' with pattern[0] = 'a' => mismatch
- no border survives, so lps[5] = 0

1. Start with lps[0] = 0 and length = 0.
2. When pattern[i] == pattern[length], increase length and write it into lps[i].
3. When they differ and length > 0, fall back to lps[length-1] and try again without moving i.
4. Only when length becomes 0 and the characters still mismatch do you write lps[i] = 0 and move on.

That procedure is linear because each fallback uses information already computed, and the length pointer only moves backward along previously discovered borders. Across the whole preprocessing pass, characters do not bounce back and forth forever.

Using LPS During Search

During the search itself, keep i in the text and j in the pattern. A match advances both. A full match means the pattern ends at i - 1, so the starting index is i - m. The interesting case is a mismatch after some matches. Instead of moving i backward or restarting j at zero immediately, set j = lps[j-1]. That preserves the largest prefix that could still match the text suffix you already consumed.

text:    a b a b a a b a b a c a
pattern: a b a b a c a

1) i=0..4, j=0..4 => five matches, so j becomes 5
2) text[5] = 'a', pattern[5] = 'c' => mismatch
3) fall back j = lps[4] = 3
4) compare text[5] = 'a' with pattern[3] = 'b' => mismatch
5) fall back j = lps[2] = 1
6) compare text[5] = 'a' with pattern[1] = 'b' => mismatch
7) fall back j = lps[0] = 0
8) compare text[5] = 'a' with pattern[0] = 'a' => match, continue
9) remaining characters complete the match starting at index 5

This is why KMP is O(n + m). Preprocessing the pattern is linear, and the search is linear because every text character is consumed at most once while the pattern pointer moves through a controlled series of fallbacks. The algorithm feels like it is retrying, but it is retrying smarter each time.

Go Implementation

The cleanest implementation keeps preprocessing and searching as two separate functions. buildLPS computes the border lengths for the pattern. KMPSearchAll scans the text and records every match, including overlapping ones, by falling back to lps[j-1] after a full hit instead of throwing away all progress.

Practice Problems

Quiz

Summary

• Naive matching wastes time whenever the pattern overlaps with itself and mismatches late.
• KMP preprocesses those self-overlaps into the LPS array, which records the longest reusable border at every position.
• During both preprocessing and search, a mismatch triggers a border fallback instead of a full restart.
• The text pointer never moves backward, which is why the full algorithm runs in O(n + m) time.
• Beyond substring search, the same prefix-function idea solves border, repetition, and concatenation problems.