KMP string search

You're scanning a large build log for an exact marker. Most candidate starts fail quickly, but one repetitive section almost matches the marker again and again. The simple search keeps comparing characters it has already seen.

KMP records which part of a failed match can still be useful. The payoff is predictable linear work, including when the text contains long runs of nearly matching prefixes. Built-in search remains the practical first choice when it already meets the application's needs.

Searching a repetitive build log

Exact substring search finds a pattern inside longer text. Trying every starting position can repeat nearly identical comparisons, costing O(nm) in the worst case for lengths n and m. Knuth–Morris–Pratt (KMP) reuses partial matches to give a linear bound, especially useful in streams and repetitive text. Prefer built-in search in ordinary Python; this lesson exposes the reuse mechanism.

A proper prefix starts at the beginning and is shorter than the whole string. table[i] records the length of the longest such prefix of pattern[:i+1] that also ends that substring. This shared prefix and suffix is a border.

Reusing the part that already matched

Let j be the previous prefix's border length. A match between pattern[i] and pattern[j] extends that border; a mismatch tries the shorter border stored at table[j-1]. Every fallback entry is already computed.

For one pattern, the construction is:

pattern = "ababac"
table = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
    while j and pattern[i] != pattern[j]:
        j = table[j - 1]
    if pattern[i] == pattern[j]:
        j += 1
    table[i] = j
print(table)

This prints [0, 0, 1, 2, 3, 0]; at the final c, the while loop tries lengths 3, 1, then 0.

For pattern 'ababac':

At position 5, the border 'aba' cannot extend with c. Its next border has length table[2]=1; that candidate also expects b, so fall back to zero. No nonempty border remains.

During search, j counts pattern characters matching the suffix of the text already read. Suppose pattern 'ababac' has matched 'ababa', so j=5, and the next text character is b. It mismatches pattern[5], or c. Fall back to table[4]=3; now the same b matches pattern[3], and the state becomes 4. The text character is consumed once; the already matched suffix 'aba' was reused.

A complete match ending at text index i starts at i-m+1. After recording it, use j = table[m-1] to retain possible overlap. For pattern 'abab', that fallback length is 2: searching 'ababab' finds starts 0 and 2 rather than missing the second match.

This independent search kernel uses the known table for abab; it keeps the border after a complete match:

text, pattern = "ababab", "abab"
table = [0, 0, 1, 2]
j, starts = 0, []
for i, char in enumerate(text):
    while j and char != pattern[j]:
        j = table[j - 1]
    if char == pattern[j]:
        j += 1
    if j == len(pattern):
        starts.append(i - len(pattern) + 1)
        j = table[j - 1]
print(starts)

The output [0, 2] shows that overlap is retained. This kernel assumes a nonempty pattern; deciding empty-pattern behavior belongs outside it.

Keeping overlaps in the result

Every fallback reduces j, spending progress gained by earlier matches; neither construction nor search repeatedly rewinds its input cursor. Construction costs O(m), search costs O(n), and auxiliary space is O(m), excluding results.

Do not reset to zero after every mismatch or every complete match: that discards useful borders and can lose overlaps or repeat work. KMP matches exact symbols; it does not handle wildcards, approximate spelling, or regular expressions. Those need different state models. Python string indices refer to code points, which need not correspond one-to-one with visible characters.

For chunked logs, carry the current match state into the next chunk: a chunk boundary is not a mismatch.