String Algorithms: KMP, Rabin-Karp, Manacher & Trie Pattern Matching
String algorithms handle text processing efficiently. From searching in documents to analyzing DNA sequences, these algorithms are essential tools in bioinformatics, search engines, natural language processing, and data compression. This guide covers the most important string algorithms, their implementation details, and practical applications.
Pattern Matching: The Fundamental Problem
Finding a pattern within a text is one of the oldest problems in computer science. The naive approach — sliding the pattern over the text and checking for a match at each position — runs in O(n × m) time, which is unacceptably slow for large texts like genomic sequences or web documents.
KMP Algorithm
The Knuth-Morris-Pratt algorithm avoids re-examining characters by preprocessing the pattern to compute a prefix function (also called the failure function). When a mismatch occurs at position j in the pattern, the prefix function tells KMP how many characters can be safely skipped — essentially, it finds the longest proper prefix of the pattern that is also a suffix of the matched portion.
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
lps = compute_lps(pattern)
i = j = 0
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
return i - j # Match found
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lpsKMP runs in O(n + m) time — it is optimal for linear-time pattern matching. The prefix function computation is O(m), and the search phase is O(n). Donald Knuth, James H. Morris, and Vaughan Pratt published the algorithm in 1977, building on earlier work by Stephen Cook.
Rabin-Karp Algorithm
Rabin-Karp uses a rolling hash to compare the pattern and text substrings efficiently. The hash of a sliding window of text is updated in O(1) time using the formula:
hash_new = (hash_old - text[i] × B^(m-1)) × B + text[i+m]
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
d, q = 256, 101 # Base and modulus
h = pow(d, m - 1, q)
p_hash = t_hash = 0
for i in range(m):
p_hash = (d * p_hash + ord(pattern[i])) % q
t_hash = (d * t_hash + ord(text[i])) % q
for i in range(n - m + 1):
if p_hash == t_hash:
if text[i:i+m] == pattern:
return i
if i < n - m:
t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
return -1Rabin-Karp averages O(n + m) but degrades to O(nm) with many hash collisions. It excels at multiple pattern matching — searching for k patterns simultaneously by storing their hashes in a hash set, maintaining O(n + km) average performance.
Richard M. Karp and Michael O. Rabin published the algorithm in 1987, making it one of the first practical randomized pattern-matching algorithms.
Boyer-Moore Algorithm
Boyer-Moore matches the pattern from right to left, using two heuristics to skip large sections of text. The bad character heuristic shifts the pattern so the mismatched character aligns with its last occurrence in the pattern. The good suffix heuristic shifts the pattern so the matched suffix aligns with its previous occurrence.
Boyer-Moore is sublinear in practice — for typical English text, it examines roughly n/m characters. Robert S. Boyer and J. Strother Moore published the algorithm in 1977, and it remains the algorithm of choice for text editors and grep-like tools due to its excellent average-case performance.
String Hashing
Hash-based string comparison enables O(1) equality checks after O(m) preprocessing. Rolling hashes extend this to O(1) substring hash computation.
Polynomial Rolling Hash
hash(s) = (s[0] × B^(n-1) + s[1] × B^(n-2) + … + s[n-1]) mod M
Choosing B and M is critical. Common choices: B = 91138233, M = 97266353 (both large primes). Double hashing with two modulus values reduces collision probability to effectively zero for competitive programming.
Rolling hashes enable O(1) longest common prefix queries between any two suffixes of a string after O(n) preprocessing, making them useful for string comparison, palindrome detection, and genome analysis.
Palindrome Algorithms
Manacher’s Algorithm
Manacher finds all palindromic substrings in O(n) time — far better than the O(n²) brute force or O(n log n) binary search with rolling hash.
The algorithm exploits symmetry: when expanding around a center, if the mirror position within a previously found palindrome has a known palindrome length, that length can be reused. Manacher maintains a center and rightmost boundary of the current palindrome, using them to skip redundant expansions.
def manacher(s):
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n
center = right = 0
for i in range(n):
if i < right:
p[i] = min(right - i, p[2 * center - i])
while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
p[i] += 1
if i + p[i] > right:
center, right = i, i + p[i]
return max(p)Manacher transforms the string by inserting separators to handle both odd and even length palindromes uniformly. The algorithm runs in O(n) time and requires O(n) space. Glenn K. Manacher published the algorithm in 1975, and it remains the fastest known approach for palindrome enumeration.
Trie: Prefix Trees
A trie (prefix tree) stores strings character by character. Each node represents a character, and paths from root to leaf represent complete strings or prefixes. Insertion and lookup are O(m) where m is the string length — independent of the number of stored strings.
Applications
Tries power autocomplete systems — find all strings with a given prefix in O(m + k) time where k is the number of results. Spell checkers use tries with Levenshtein distance computation for fuzzy matching. IP routing tables use binary tries (Patricia tries) for longest prefix matching. Compressed tries (radix trees) merge single-child nodes to reduce memory usage.
Suffix Arrays and LCP Arrays
A suffix array lists all suffixes of a string in sorted order. Constructed in O(n log n) or O(n) time (SA-IS algorithm), the suffix array enables efficient substring search in O(m log n) time via binary search.
The LCP (Longest Common Prefix) array stores the length of the longest common prefix between adjacent suffixes in the suffix array. Together, suffix array and LCP array solve many string problems: longest repeated substring, longest common substring, number of distinct substrings, and pattern matching.
Aho-Corasick: Multiple Pattern Matching
The Aho-Corasick algorithm extends KMP to search for multiple patterns simultaneously. It builds a trie of all patterns, then adds failure links (similar to KMP’s prefix function) that point to the longest proper suffix that is also a prefix of some pattern.
Aho-Corasick runs in O(n + m + z) time where n is text length, m is total pattern length, and z is the number of matches found. It is used in intrusion detection systems (Snort, Suricata), virus scanners, and content filtering — anywhere you need to match against thousands of patterns simultaneously.
# Conceptual usage — find all occurrences of multiple patterns
patterns = ["he", "she", "his", "hers"]
aho = build_aho_corasick(patterns)
matches = aho.search("ushers")
# Finds "she" at 0, "he" at 1, "hers" at 2The algorithm is linear regardless of the number of patterns, making it the optimal solution for multi-pattern matching.
Frequently Asked Questions
Which pattern-matching algorithm is best for searching in a text editor?
Boyer-Moore is typically best for interactive text editors. Its sublinear average-case performance means it scans fewer characters than the pattern length in typical use. For very short patterns (1-3 characters), memchr or SIMD-based approaches are faster.
How does Rabin-Karp handle hash collisions?
When a hash match occurs, Rabin-Karp verifies the match by character-by-character comparison. False positives only affect performance (extra comparisons), not correctness. Double hashing reduces false positives to negligible levels.
What is the difference between KMP and Boyer-Moore?
KMP matches left to right and is optimal in the worst case (O(n+m)). Boyer-Moore matches right to left and is sublinear in the average case but can be O(nm) in the worst case without the good suffix heuristic. For typical text search, Boyer-Moore is faster. For patterns with small alphabets or guaranteed worst-case performance, KMP is preferred.
When should I use a trie versus a hash table for string storage?
Tries support prefix queries (find all strings starting with “excel”), which hash tables cannot answer efficiently. Tries also use less memory than hash tables for large sets of strings with common prefixes. Hash tables are faster for exact membership queries and more memory-efficient for random strings.
What is the fastest algorithm for finding the longest palindrome in a string?
Manacher’s algorithm runs in O(n) time, which is asymptotically optimal. The only faster approach is to use suffix automaton or suffix array with LCP queries, both of which are more complex to implement and have higher constant factors.