String Matching Algorithms
The problem
Finding whether and where a pattern occurs inside a larger text by naively comparing the pattern at every possible starting position wastes work re-examining characters that a smarter algorithm could rule out or reuse — this matters enormously once text and patterns are large (a genome, a full-text search index).
Why now
Strings and text already established that a string is a sequence of characters; naive search over that sequence is straightforward but slow. Modular arithmetic already gave a way to compute a compact numeric fingerprint efficiently — string matching is where that fingerprint (a rolling hash) gets used to skip comparisons that are almost certainly going to fail anyway.
Mental model
Naive string matching slides the pattern one position at a time and rechecks everything — O(n·m) in the worst case. Rabin-Karp instead computes a rolling hash of each window in O(1) per shift (reusing the previous window's hash via modular arithmetic) and only does a full character comparison when hashes match, turning most positions into a single fast integer comparison instead of a full re-scan. KMP takes a different approach, precomputing how much of a failed match can be reused instead of restarting from scratch.
Requires
- Strings & TextProgramming Fundamentals
String matching algorithms operate on the character sequences strings-and-text already defined; you need string indexing and comparison fluency before an algorithm for searching within them is meaningful.
- Modular ArithmeticMathematical Thinking
Rabin-Karp's rolling hash is a direct, practical application of modular arithmetic — computing each window's hash incrementally via the exact mod-based update rule already covered, not recomputing it from scratch.
Used in
- Text editors' and IDEs' find/search functionality on large files
- grep and other command-line text search tools
- Plagiarism detection and DNA sequence matching
- Intrusion detection systems scanning network traffic for known attack signatures
Projects
- Implement naive string matching and Rabin-Karp for the same pattern-search problem, and benchmark both on a large text with a rare pattern
- Trace through KMP's failure function by hand for a short pattern, showing exactly how much re-scanning it avoids after a partial match fails
Examples
- Searching for a 10-character pattern in a 1,000,000-character text naively can take up to ~10,000,000 character comparisons; Rabin-Karp's rolling hash reduces most positions to one integer comparison
- KMP searching for 'AABA' after a partial match failure at the 4th character reuses the fact that 'AAB' was already matched, instead of restarting the whole comparison from the next position
Resources
Mastery checklist
- I can implement naive string matching and explain its worst-case cost
- I can implement Rabin-Karp using a rolling hash and explain how the hash updates in O(1) per shift
- I can explain, at a high level, what KMP's failure function avoids re-doing
- I can choose an appropriate string matching approach given text and pattern size