44. Compare brute-force, Rabin-Karp and KMP string matching.
MediumString algorithms
Technical
Show model answer
Brute force tries every alignment: O(nm) worst case. Rabin-Karp compares rolling hashes of each window and only checks characters on a hash match: O(n + m) average, good for multiple patterns. KMP precomputes a prefix (failure) table so the text pointer never moves backwards: O(n + m) worst case. Boyer-Moore skips ahead using the last character and is fast in practice.