String matching algorithms compared
String hashing, Rabin-Karp, KMP, the Z algorithm, Manacher and tries: what each preprocesses, what it guarantees, and the problem shape each is built for.
| Algorithm | Time | Space | Preprocesses | Guarantee | Problem shape | Difficulty |
|---|---|---|---|---|---|---|
| String HashingString hashing | O(n) | O(n) | Text (prefix hashes) | Probabilistic | Any two substrings compared in O(1) | Intermediate |
| Rabin-KarpRolling hash matching | O(n+m) average | O(1) | Pattern (one hash) | Average O(n+m) | Several patterns at once | Intermediate |
| KMPPrefix-function matching | O(n+m) | O(m) | Pattern (failure function) | Worst case O(n+m) | One pattern, streaming text | Hard |
| Z-AlgorithmThe Z function | O(n+m) | O(n) | Pattern + text (concatenated) | Worst case O(n+m) | Longest prefix match at every position | Hard |
| ManacherLongest palindrome | O(n) | O(n) | Text (with separators) | O(n) | Palindromes | Hard |
| Trie ApplicationsTries in practice | O(L) | O(ΣL) | Dictionary (all patterns) | O(L) per query | Prefix queries, dictionary lookups | Intermediate |
When to pick which
Comparing many substring pairs, longest repeated substring, or pairing with binary search. Use two moduli to make collisions negligible.
Many equal-length patterns at once (plagiarism, signatures): put every pattern hash in a set and roll over the text once. For one pattern it is no better than KMP.
The standard answer for one pattern; the text can be streamed one character at a time. The failure function also yields periods and shortest palindromic completions.
When the question is 'how far does each position match the start': string periods, smallest repeating unit, prefix occurrence counts. More direct than KMP for these.
Longest palindromic substring, palindrome radius at every centre, counting palindromic substrings. It does palindromes and nothing else.
Autocomplete, counting by prefix, whether a word can be built from a dictionary. Best when the pattern set is fixed and queried many times.
Choosing guide
- One pattern, one text → KMP. For something simpler use the built-in
find/strstr; they are usually linear too. - Many patterns → equal lengths: a Rabin-Karp hash set; mixed lengths found in one pass: Aho-Corasick (a trie plus KMP, not covered on this site).
- Substring equality, repeats, comparisons → string hashing, the only O(1) way to compare two arbitrary substrings, at the price of being probabilistic.
- Palindromes → Manacher. Centre expansion at O(n²) is fine for n ≤ 1000; get it right first, then switch.
- Prefixes → a trie. Suffixes or arbitrary substring structure → suffix arrays or suffix automata (not covered on this site).