KMP: reuse a matched prefix
Picture
Pattern abab has matched, then the next character differs. Its suffix ab is also a prefix we already know.
Predict
Why not restart the pattern at zero after every mismatch?
Walk through the small example
A matched suffix may already equal a prefix. The pattern’s prefix-suffix borders describe how much matched work survives a mismatch.
Mental model and complete Python solution
The prefix table is an emergency staircase inside the pattern. A mismatch walks down to the longest smaller prefix already justified by the matched suffix.
What the function promises: Return all starting positions of exact matches. Empty pattern matches every boundary.
def prefix_table(pattern):
table = [0] * len(pattern)
matched = 0
for i in range(1, len(pattern)):
while matched and pattern[i] != pattern[matched]:
matched = table[matched-1]
if pattern[i] == pattern[matched]:
matched += 1
table[i] = matched
return table
def kmp_find(text, pattern):
if pattern == "": return list(range(len(text)+1))
table, matched, answer = prefix_table(pattern), 0, []
for i, char in enumerate(text):
while matched and char != pattern[matched]:
matched = table[matched-1]
if char == pattern[matched]:
matched += 1
if matched == len(pattern):
answer.append(i-len(pattern)+1)
matched = table[matched-1]
return answer
assert kmp_find("ababa","aba") == [0,2]
assert prefix_table("ababaca") == [0,0,1,2,3,0,1]Work and storage: O(n+m) time and O(m) prefix-table space.
When to recognize it: The pattern’s prefix-suffix borders describe how much matched work survives a mismatch.
Check before applying it: Incorrect fallback after a full match misses overlaps; empty-pattern behavior must be defined.
Change one rule
Match many patterns at once.
See what changes
Use a trie with failure links, such as Aho–Corasick.
Connect
Rolling hash: compare windows cheaply: Compare deterministic border reuse with probabilistic fingerprints.
tries: Both reuse prefix structure, but KMP matches one pattern through text.