String matching finds all occurrences of a pattern P (length m) in a text T (length n). The main algorithms are the naive method, Rabin–Karp, Knuth–Morris–Pratt (KMP), finite automaton matching and Boyer–Moore.
1. Naive (brute force) algorithm
Slide the pattern over the text one position at a time; at each shift \(s = 0\) to \(n - m\), compare P with T[s+1 .. s+m] character by character. Simple, no preprocessing. Worst case \(O((n - m + 1)m)\), e.g. T = aaaa…a, P = aaab.
2. Rabin–Karp algorithm
Treat strings as numbers and compare hash values instead of characters. Compute \(h(P)\) and the hash of each m-length window of T. The window hash is updated in \(O(1)\) using a rolling hash:
\[t_{s+1} = (d(t_s - T[s+1]h) + T[s+m+1]) \bmod q\]
Only when the hashes match are characters compared (to rule out a spurious hit). Average \(O(n + m)\), worst \(O((n - m + 1)m)\). Useful for searching many patterns.
3. Knuth–Morris–Pratt (KMP) algorithm
Preprocesses the pattern into a prefix (failure) function \(\pi[q]\) = length of the longest proper prefix of P[1..q] that is also its suffix. On a mismatch, the pattern shifts using \(\pi\) instead of restarting, so the text pointer never moves back. Example: P = ababaca has \(\pi\) = 0 0 1 2 3 0 1. Time \(O(m)\) for preprocessing plus \(O(n)\) for matching.
4. Finite automaton matching
Build a DFA for P whose states 0..m record how much of P has been matched. Scan the text once, making one transition per character; reaching state m means a match. Matching is \(O(n)\); building the transition table takes \(O(m|\Sigma|)\).
5. Boyer–Moore algorithm
Compares the pattern from right to left and uses the bad-character and good-suffix rules to skip large parts of the text. Very fast in practice for large alphabets (sublinear on average).
| Algorithm | Preprocessing | Matching (worst) |
|---|---|---|
| Naive | none | \(O((n-m+1)m)\) |
| Rabin–Karp | \(O(m)\) | \(O((n-m+1)m)\) |
| Finite automaton | \(O(m|\Sigma|)\) | \(O(n)\) |
| KMP | \(O(m)\) | \(O(n)\) |