DSA & Implementation · core
String Matching
Finding a pattern in text in linear time — KMP's failure function and Rabin-Karp's rolling hash.
Mental model
Naive matching restarts the pattern after every mismatch, throwing away what the prefix already proved. KMP precomputes how far it can safely jump using the longest proper prefix that is also a suffix, so the text pointer never moves backwards. Rabin-Karp takes the other route: hash a window, roll the hash in O(1) as it slides, and only compare characters when hashes agree — which makes it the natural choice for multi-pattern search and the reason collisions must still be checked.
How to study String Matching
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare String Matching with Trie, Arrays & Hashing. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Rabin-Karp substring search and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
grep, plagiarism and duplicate detection, and the substring primitives inside every editor.
Common mistakes
- Treating a Rabin-Karp hash match as a match — you must verify the characters, or an adversarial input degrades to O(nm)
- Building the KMP failure table against the text instead of the pattern
- Using a rolling hash modulo a small constant, making collisions common enough to matter
- Reaching for KMP when a library indexOf is both correct and faster in practice
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Rabin-Karp substring search
Implement findAll(text, pattern) returning every start index where pattern occurs, using a rolling hash. You MUST verify a character-by-character match on every hash hit — a hash collision is not a match.
Expected evidence: findAll('abababa','aba') -> [0,2,4]
Open the interactive drill →Review prompts
- Rabin-Karp finds a window whose hash equals the pattern's hash. Why is it wrong to report a match, and what is the worst case if you skip the check?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.