Never re-read what you already matched
String Matching: KMP & Rabin-Karp
The analogy
Naively, when a match fails you slide the pattern one place right and start over from its first letter — throwing away everything you just learned. KMP precomputes how much of the pattern is its own prefix, so on a mismatch it knows exactly how far it can jump without re-reading a single character of the text.
Visualizer
Falling back inside the pattern
step 1 / 10| text | A | B | A | B | A | B | C | A | B | A | B |
| pattern | A | B | A | B | C | ||||||
| lps | 0 | 0 | 1 | 2 | 0 |
Search for "ABABC" in "ABABABCABAB". The naive method, on a mismatch, slides the pattern one place right and restarts from its first character — throwing away everything it just learned.naive: O(n*m)
def build_lps(p):
lps = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k and p[i] != p[k]:
k = lps[k - 1] # fall back within the pattern
if p[i] == p[k]:
k += 1
lps[i] = k
return lps
def kmp(text, p):
lps, k, hits = build_lps(p), 0, []
for i, ch in enumerate(text): # i NEVER goes backwards
while k and ch != p[k]:
k = lps[k - 1]
if ch == p[k]:
k += 1
if k == len(p):
hits.append(i - k + 1)
k = lps[k - 1]
return hits
# O(n + m). Rolling hash alternative:
# h = (h - ord(old) * pow(B, m-1, M)) * B + ord(new) mod MCheck yourself
In KMP, can the text pointer ever move backwards?