KMP and the failure function

Naive substring matching tries the pattern at every position in the text:

def naive(text, pat):
    n, m = len(text), len(pat)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pat[j]:
            j += 1
        if j == m:
            return i
    return -1

Its worst case is O(n·m), and the input that produces it is short: text "a" * n, pattern "a" * (m - 1) + "b". Every start position matches m - 1 characters and then fails on the last. At n = 10⁶ and m = 1,000 that is 10⁹ character comparisons — roughly 10 seconds at 10⁸ operations per second.

The waste is exact. After matching ababa and failing on the sixth character, we know five characters of the text. Restarting at i + 1 reads them again, having deliberately forgotten what they were.

The failure function

lps[i] is the length of the longest proper prefix of pat[0..i] that is also a suffix of pat[0..i]. Proper means "not the whole string" — without that word the answer is always i + 1 and the table says nothing.

For the pattern ababaca:

i	pat[0..i]	longest proper prefix that is also a suffix	lps[i]
0	a	—	0
1	ab	—	0
2	aba	a	1
3	abab	ab	2
4	ababa	aba	3
5	ababac	—	0
6	ababaca	a	1

Read row 4 as the useful one: after matching ababa, the last three characters of what we matched are also the first three characters of the pattern. So a mismatch on the next character does not throw away five characters of progress — it throws away two, and keeps three.

def build_lps(pat):
    lps = [0] * len(pat)
    length = 0                                  # length of the current border
    for i in range(1, len(pat)):
        while length and pat[i] != pat[length]:
            length = lps[length - 1]            # fall back, do not restart
        if pat[i] == pat[length]:
            length += 1
        lps[i] = length
    return lps

Two pointers: i walks the pattern once and never moves back; length holds the border found so far. Step i = 5 on ababaca is the one worth tracing. length is 3, and pat[5] is c against pat[3] which is b — no match, so fall back to lps[2] = 1. Now c against pat[1], which is b — no match, fall back to lps[0] = 0. Now c against pat[0], which is a — no match, and length is already 0, so lps[5] = 0. Three comparisons, no rescan.

Resume instead of restart

On a mismatch after j matched characters, do not set j to 0. Set it to lps[j-1] and compare again at the same text position. The pattern slides right by j - lps[j-1], and the text pointer does not move at all.

A mismatch at pattern index 5 slides the pattern right by two, and matching resumes at index 3 without moving the text pointer100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

def kmp_search(text, pat):
    if not pat:
        return 0
    lps = build_lps(pat)
    j = 0
    for i, ch in enumerate(text):
        while j and ch != pat[j]:
            j = lps[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            return i - j + 1
    return -1

The loop variable i only increases. Every character of the text is read exactly once, which is the property the whole algorithm exists to buy.

Why this is O(n + m) and not O(n·m)

The inner while sits inside a loop over the text, so counting the innermost line appears to give O(n·m). It does not, and the reason is an accounting argument rather than an inspection of the code.

Watch j. The outer loop increases it by at most 1 per iteration, so across the whole search it goes up at most n times. Every iteration of the inner loop sets j = lps[j-1], and lps[j-1] is strictly less than j, so each of those decreases j by at least 1. A quantity that starts at 0, rises at most n times, and never goes negative can fall at most n times. The inner loop body runs at most n times over the entire search, not per position. Matching is O(n), the build is the same argument over the pattern at O(m), and together they are O(n + m).

Back to the numbers: n = 10⁶ and m = 1,000 gives 1,001,000 steps instead of 10⁹ — about 10 ms against 10 seconds, a factor of a thousand.

Be honest about when that factor shows up. On English text, naive matching is usually fine, because a mismatch typically arrives on the first or second character and the real cost is close to n. The adversarial shape is repetition: binary strings, DNA over four letters, "aaaa…". Say this in an interview before someone else does.

The other thing the table buys

The shortest repeating unit of a pattern of length m is m - lps[m-1], whenever that value divides m. For abcabcabc, m = 9 and lps[8] = 6, so the period is 9 - 6 = 3, and 3 divides 9 — the string is abc three times. For abcabca, m = 7 and lps[6] = 4, giving 3, which does not divide 7, so the string is not a whole number of repeats. Two lines of code, and it answers "is this string built by repeating a substring" without trying every divisor.

In an interview

State the definition of lps before writing the build loop. Most people can write the two-pointer code from memory and then cannot say what the array means, which the interviewer reads — correctly — as recall rather than understanding. The sentence to have ready is: "lps[i] is the longest proper prefix of the pattern ending at i that is also a suffix, so on a mismatch I already have that many characters matched and can resume there."

Then volunteer the amortised argument. It is the actual content of the question: the code looks quadratic, and explaining why it is linear is the part that separates candidates. Follow it with the honest note about naive being fine on natural text — the same judgement call as choosing expansion over Manacher in palindromes.

The mistake that loses points: setting j = 0 on a mismatch, or moving the text index backwards. Both turn the algorithm back into the naive one while keeping the table that was built to avoid it, and the result still passes small tests.

Check yourself

What is lps for aabaaac?

[0, 1, 0, 1, 2, 2, 0]. Check index 5: aabaaa has aa as both a proper prefix and a suffix, and aab is not a suffix, so 2.

A mismatch happens after 7 matched characters and lps[6] = 4. How far does the pattern move, and where does the text pointer go?

The pattern slides right by 7 - 4 = 3. The text pointer does not move; the next comparison is the same text character against pat[4].

You are searching a 10 MB log for a 12-character token. Is KMP worth writing?

Probably not. Naive is O(n·m) in theory but close to O(n) on log text, and the standard library's substring search is already a tuned linear-time algorithm. Reach for KMP when the alphabet is small and repetitive, or when the failure function itself is what you need — periods, borders, or overlap between two strings.