String algorithms: matching, hashing and tries
Move past naive matching with KMP and rolling hashes, index prefixes with a trie, and know when a suffix structure is warranted.
Naive, KMP and Rabin-Karp
def naive_search(text: str, pattern: str) -> list[int]:
"""O(n*m) worst case: every mismatch can restart the scan from scratch."""
out: list[int] = []
m = len(pattern)
if m == 0:
return out
for i in range(len(text) - m + 1):
if text[i:i + m] == pattern:
out.append(i)
return out
def build_lps(pattern: str) -> list[int]:
"""lps[i] = the length of the longest proper prefix of pattern[:i+1]
that is also a suffix. This is what lets KMP skip re-comparisons."""
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1] # fall back, do not restart
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text: str, pattern: str) -> list[int]:
"""O(n + m): the text index never moves backwards."""
if not pattern:
return []
lps = build_lps(pattern)
out: list[int] = []
i = j = 0 # i indexes text, j indexes pattern
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
out.append(i - j)
j = lps[j - 1] # continue: there may be overlaps
elif j > 0:
j = lps[j - 1]
else:
i += 1
return out
def rabin_karp(text: str, pattern: str) -> list[int]:
"""Rolling hash: expected O(n + m), and it generalises to pattern sets."""
m, n = len(pattern), len(text)
if m == 0 or m > n:
return []
base, mod = 256, 1_000_000_007
high = pow(base, m - 1, mod) # weight of the leading character
ph = th = 0
for i in range(m):
ph = (ph * base + ord(pattern[i])) % mod
th = (th * base + ord(text[i])) % mod
out: list[int] = []
for i in range(n - m + 1):
if ph == th: # hashes match: verify the actual text
if text[i:i + m] == pattern:
out.append(i)
if i < n - m:
th = (th - ord(text[i]) * high) % mod
th = (th * base + ord(text[i + m])) % mod
return out
if __name__ == "__main__":
print(naive_search("ababcababc", "abc")) # [2, 7]
print(build_lps("ababaca")) # [0,0,1,2,3,0,1]
print(kmp_search("ababcababc", "abc")) # [2, 7]
print(rabin_karp("ababcababc", "abc")) # [2, 7]| Algorithm | Preprocessing | Search | Worst case |
|---|---|---|---|
| Naive | None | O(n * m) | O(n * m) |
| KMP | O(m) | O(n) | O(n + m) |
| Rabin-Karp | O(m) | O(n) expected | O(n * m) on adversarial collisions |
| Boyer-Moore | O(m + alphabet) | Sublinear on average | O(n * m) |
| Aho-Corasick | O(sum of patterns) | O(n + matches) | Linear: many patterns at once |
| Z-algorithm | O(n + m) | O(n + m) | Linear: cleaner than KMP to write |
- The LPS table is the whole of KMP. Build it on the pattern alone, and test it separately: a wrong table produces plausible but wrong matches.
- KMP's invariant is that the text pointer only moves forward. That is what makes the bound linear, and it is also why the algorithm works on a stream.
text[i:i+m]creates a copy in Python, so the naive version has an extra factor of m in both time and allocation. A rolling hash avoids the copy until the hashes match.- Rabin-Karp must verify a hash hit against the real text, or a collision becomes a false positive. Use two different moduli if the input is adversarial.
Tries
class TrieNode:
__slots__ = ("children", "is_word", "count")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_word = False
self.count = 0 # words passing through this node
class Trie:
"""Prefix tree: O(len(key)) insert and lookup, shared prefixes stored once."""
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.count += 1
node.is_word = True
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def count_prefix(self, prefix: str) -> int:
node = self._walk(prefix)
return node.count if node else 0
def _walk(self, prefix: str) -> TrieNode | None:
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def words_with_prefix(self, prefix: str, limit: int = 10) -> list[str]:
node = self._walk(prefix)
out: list[str] = []
if node is None:
return out
def dfs(current: TrieNode, path: list[str]) -> None:
if len(out) >= limit:
return
if current.is_word:
out.append("".join(path))
for ch, child in current.children.items():
path.append(ch)
dfs(child, path)
path.pop()
dfs(node, list(prefix))
return out
if __name__ == "__main__":
t = Trie()
for w in ["cat", "car", "card", "care", "dog"]:
t.insert(w)
print(t.search("car"), t.search("ca"))
print(t.count_prefix("car"))
print(t.words_with_prefix("car")) # ['car', 'card', 'care']A trie trades memory for time. Each node is an object and each edge a dictionary entry, so a million short words can cost far more than the list of strings. A compressed trie (a radix tree or Patricia trie) removes the chains of single-child nodes and is what production prefix indexes actually use.
Suffix structures and rolling hashes
def longest_repeated_substring(s: str) -> str:
"""Binary search the length, checking with a rolling hash. O(n log n)."""
n = len(s)
if n < 2:
return ""
base, mod = 131, (1 << 61) - 1
def exists(length: int) -> str | None:
if length == 0:
return ""
seen: dict[int, int] = {}
h = 0
high = pow(base, length - 1, mod)
for i, ch in enumerate(s):
h = (h * base + ord(ch)) % mod
if i >= length:
h = (h - ord(s[i - length]) * high) % mod
if i >= length - 1:
start = i - length + 1
if h in seen and s[seen[h]:seen[h] + length] == s[start:start + length]:
return s[start:start + length]
seen[h] = start
return None
lo, hi, best = 1, n - 1, ""
while lo <= hi:
mid = (lo + hi) // 2
found = exists(mid)
if found is not None:
best = found
lo = mid + 1
else:
hi = mid - 1
return best
# Suffix arrays: sort all suffixes, then answer substring queries with a binary
# search on the sorted order. Building one in O(n) needs SA-IS or DC3; a
# simple O(n log^2 n) version is enough for most work and far easier to get right.
def suffix_array_simple(s: str) -> list[int]:
return sorted(range(len(s)), key=lambda i: s[i:])
# The rule of thumb:
# - one pattern, one text -> KMP or Python's built-in find (Boyer-Moore
# under the hood in CPython's fastsearch)
# - many patterns over one text -> Aho-Corasick
# - repeated substring queries -> suffix array or a suffix automaton
# - human names, small alphabets, memory tight -> a trie or a radix tree
if __name__ == "__main__":
print(longest_repeated_substring("banana")) # ana
print(suffix_array_simple("banana"))⚠️
Rolling hashes are probabilistic. A single modulus can be defeated deliberately: an attacker who knows your base and modulus can construct two different substrings with the same hash and turn a linear check into a quadratic one. Use a random base chosen per run, or two independent moduli, for anything exposed to untrusted input.
FAQ
Why prefer KMP over the language's built-in search?
Usually you should not: a good standard library implementation is faster and better tested. KMP matters when you need the LPS table itself, when you must process a stream, or when you are implementing the search for a platform that lacks one.
Do I need a suffix automaton?
Only for many substring queries over one fixed text: distinct substring counts, longest common substring of several strings, or counting occurrences of arbitrary patterns. For one-off searches, KMP or a hash is much less code.
Related
Dynamic programming patterns: knapsack, edit distance, LCS Verifying and benchmarking algorithms
Last refreshed 2026-09-18.