The idea
Naive search restarts after every mismatch. KMP keeps a counter j, the number of pattern characters currently matched, and on a mismatch falls back to the next-best partial match using the prefix function pi. pi[i] is the length of the longest proper border of pattern[:i+1] (a border is a prefix that is also a suffix). The text index only moves forward, which is what makes the whole search linear.
For aabaa, the border lengths are: a has none (0), aa has a (1), aab has none (0), aaba has a (1), and aabaa has aa (2). That gives pi = [0, 1, 0, 1, 2]. The next section builds it one cell at a time.
Approach
- Build
pi for the pattern (O(m)).
- For each text character
c: while j > 0 and c differs from pattern[j], set j = pi[j-1]. Then, if c == pattern[j], increment j.
- When
j == m, record i - m + 1, then set j = pi[j-1] (not 0) so overlapping matches are still found.
- Handle the special cases first: an empty pattern, and a pattern longer than the text.
Building pi by hand
pi is built with the same trick as the search: the pattern is searched against itself. Keep k, the length of the border of the prefix seen so far, and look at the next character p[i]:
- If
p[i] == p[k], the border grows by one: k += 1.
- If not, the current border (the first
k characters of the pattern, which also end at position i - 1) cannot be extended by p[i], so try a shorter border. The shorter candidates are exactly the borders of the border. Because the last k characters just read equal p[:k], a border of those characters is also a border of p[:k], and pi[k-1] is the longest of those. So k = pi[k-1] jumps straight to the next-longest candidate, and no shorter-but-valid candidate is skipped, since any candidate longer than pi[k-1] and shorter than k would contradict pi[k-1] being the longest border of p[:k].
- If
k reaches 0 and p[i] != p[0], then pi[i] = 0.
For aabaa the run below shows each step. At i=2, b differs from p[1] = a, so k falls from 1 to pi[0] = 0 and pi[2] = 0. At i=3, a == p[0], so k = 1. At i=4, a == p[1], so k = 2.
The search loop applies the same rule to the text, with j playing the role of k.
Code
python
import random
from typing import List
def prefix_function(p: str) -> List[int]:
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def prefix_function_traced(p: str) -> List[int]:
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
print(f" i={i} {p[i]!r} != p[{k}]={p[k]!r}: k {k} -> {pi[k - 1]}")
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
print(f" i={i} {p[i]!r}: pi[{i}]={k} (prefix {p[:k]!r} = suffix {p[i - k + 1:i + 1]!r})")
return pi
def kmp_search(text: str, pattern: str) -> List[int]:
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1))
if m > n:
return []
pi = prefix_function(pattern)
hits, j = [], 0 # j = how many pattern chars currently match
for i, c in enumerate(text):
while j > 0 and c != pattern[j]:
j = pi[j - 1]
if c == pattern[j]:
j += 1
if j == m:
hits.append(i - m + 1)
j = pi[j - 1] # keep the longest border so overlapping matches are found
return hits
def kmp_search_traced(text: str, pattern: str) -> List[int]:
pi = prefix_function(pattern)
hits, j = [], 0
for i, c in enumerate(text):
while j > 0 and c != pattern[j]:
print(f" i={i} {c!r} != pattern[{j}]={pattern[j]!r}: j {j} -> {pi[j - 1]}")
j = pi[j - 1]
if c == pattern[j]:
j += 1
line = f" i={i} {c!r}: j={j}"
if j == len(pattern):
hits.append(i - len(pattern) + 1)
j = pi[j - 1]
line += f" -> MATCH at {hits[-1]}, j reset to {j}"
print(line)
return hits
def text_comparisons(text: str, pattern: str) -> int:
pi = prefix_function(pattern)
j = count = 0
for c in text:
while j > 0 and c != pattern[j]:
count += 1
j = pi[j - 1]
count += 1
if c == pattern[j]:
j += 1
if j == len(pattern):
j = pi[j - 1]
return count
print("building pi('aabaa'), pi[0] = 0:")
print("pi('aabaa') =", prefix_function_traced("aabaa"))
print("trace of 'aabaa' in 'aabaabaaa':")
print(kmp_search_traced("aabaabaaa", "aabaa"))
print(kmp_search("ababa", "aba"), kmp_search("abc", ""), kmp_search("abc", "abcd"))
for n in (1000, 2000, 4000):
c = text_comparisons("a" * n, "a" * 99 + "b")
print(f"n={n}: character comparisons={c}, 2n={2 * n}")
random.seed(11)
for _ in range(2000):
t = "".join(random.choice("ab") for _ in range(random.randint(0, 14)))
p = "".join(random.choice("ab") for _ in range(random.randint(0, 6)))
expected = [i for i in range(len(t) - len(p) + 1) if t.startswith(p, i)]
assert kmp_search(t, p) == expected, (t, p)
print("2000 random cases match str.startswith scan")
Output:
text
building pi('aabaa'), pi[0] = 0:
i=1 'a': pi[1]=1 (prefix 'a' = suffix 'a')
i=2 'b' != p[1]='a': k 1 -> 0
i=2 'b': pi[2]=0 (prefix '' = suffix '')
i=3 'a': pi[3]=1 (prefix 'a' = suffix 'a')
i=4 'a': pi[4]=2 (prefix 'aa' = suffix 'aa')
pi('aabaa') = [0, 1, 0, 1, 2]
trace of 'aabaa' in 'aabaabaaa':
i=0 'a': j=1
i=1 'a': j=2
i=2 'b': j=3
i=3 'a': j=4
i=4 'a': j=5 -> MATCH at 0, j reset to 2
i=5 'b': j=3
i=6 'a': j=4
i=7 'a': j=5 -> MATCH at 3, j reset to 2
i=8 'a' != pattern[2]='b': j 2 -> 1
i=8 'a': j=2
[0, 3]
[0, 2] [0, 1, 2, 3] []
n=1000: character comparisons=1901, 2n=2000
n=2000: character comparisons=3901, 2n=4000
n=4000: character comparisons=7901, 2n=8000
2000 random cases match str.startswith scan
Worked trace: aabaa in aabaabaaa
The printed table shows pi('aabaa') = [0, 1, 0, 1, 2]. The first five characters match and give a hit at 0. The code then sets j = pi[4] = 2, because the last two matched characters aa are also the pattern's first two, and continues with b, a, a, producing the overlapping hit at 3 without looking back at the text. At the last character, a differs from pattern[2] = b, so j falls from 2 to pi[1] = 1, then a matches pattern[1], leaving j = 2. Result: [0, 3].
Why the search is O(n + m)
j goes up by at most 1 per text character, so over the whole run it rises at most n times. Every fallback lowers it, so there can be at most n fallbacks in total, even though one character may trigger several. The loop therefore does at most n comparisons that advance plus n that fall back. The measurement above, taken on text aaaa...a with pattern aaa...ab (99 a's then b), shows character comparisons of 1,901, 3,901 and 7,901 for n = 1,000, 2,000 and 4,000, always under 2n. Building pi is O(m) by the same argument. Space is O(m) for pi, plus the output list.
Edge cases
- Empty pattern: returns
[0, 1, ..., n] (every gap), consistent with str.find(""). State the convention.
- Pattern longer than text: returns
[] immediately (also avoids a useless pi build).
- Overlapping matches:
ababa / aba gives [0, 2]. If the code reset j = 0 after a match, the second hit would be lost. On aabaabaaa with pattern aabaa that variant reports only [0] and misses the match at 3.
- Pattern equal to text, single-character pattern and repeated characters (
aaaa) all work, since the same loop handles them.
- Unicode: indexing is by Python code point, so results are code point offsets, not byte offsets.
Common mistakes
if instead of while in the fallback loop.- Reading
pattern[j] when j == m (IndexError); resetting j right after a match prevents it.
- Using
pi[j] instead of pi[j-1].
- Building
pi for the single string pattern + '#' + text, a well-known alternative way to search. Every value of pi that equals len(pattern) marks a match ending there, and the # separator stops any border from running past the pattern, so it must not appear in either string. The shipped code uses the two-pass search instead, which needs no separator.
The function was checked against a str.startswith scan on 2,000 random binary strings (final printed line).
Running the code
Python 3.12, standard library only.
