DSA & Algorithms
Part 6 of 16 · DSA Advanced & Company FavoritesStrings - Parsing, Rolling Hash & KMP intuition
String parsing patterns, Rabin-Karp rolling hash, and KMP LPS intuition for interviews.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You search or scan a string many times
Prefer
Preprocess, then scan once
KMP uses the LPS table. Rabin-Karp rolls a hash.
- LPS is the longest proper prefix that is also a suffix.
- A hash collision must be checked.
- A parser prompt may want a stack, not KMP.
Alternative
Slide the pattern one character at a time
The naive scan is O(n*m) and restarts after every mismatch.
- You rebuild the window from scratch.
- You ignore the border you already matched.
- You treat a hash hit as proof.
Preprocess the pattern
Then the text is a single scan.
- 1
Build LPS
Border length for each prefix. - 2
On mismatch, jump
Use LPS instead of restarting at 0. - 3
Or roll a hash
Verify when the hashes match.
Overview
String parsing patterns, Rabin-Karp rolling hash, and KMP LPS intuition for interviews.
When companies ask this
Recognition cues: find pattern in text; repeated substring; parse calculator / decode string; anagram window (also sliding window).
Mental model
Decisions
- 1
1. Naive scan restarts
- next2. Preprocess how?
- ?
2. Preprocess how?
- hash3. Roll a Rabin-Karp hash
- border4. KMP jumps with LPS
- 3
3. Roll a Rabin-Karp hash
- 4
4. KMP jumps with LPS
Lesson map
Strings - Parsing, Rolling Hash & KMP intuition
String parsing patterns, Rabin-Karp rolling hash, and KMP LPS intuition for interviews.
Architecture. 1. Naive scan restarts Ready. 2. Preprocess how? Ready. 3. Roll a Rabin-Karp hash Ready. 4. KMP jumps with LPS Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Naive["1. Naive scan restarts Ready"] Which["2. Preprocess how? Ready"] RK["3. Roll a Rabin-Karp hash Ready"] KMP["4. KMP jumps with LPS Ready"] Naive -->|continues| Which Which -->|hash| RK Which -->|border| KMP
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- KMP O(n+m); Rabin-Karp average O(n+m), worst O(nm) with collisions - always verify.
- Pitfalls: negative mod; off-by-one LPS; confusing KMP with Z-algorithm.
Interviewer traps
LeetCode drill (real problems)
- Implement strStr
- Repeated Substring Pattern
- Longest Happy Prefix
- Shortest Palindrome
- Decode String
- Basic Calculator II
- Valid Anagram
- Longest Substring Without Repeating Characters
- Minimum Window Substring
YouTube
Interview Q&A
LPS meaning?
Answer
For each prefix, longest proper prefix that is also suffix.
KMP mismatch?
Answer
If j > 0 jump j to lps[j-1] and keep i; if j == 0 advance i. Never recheck matched text.
Rabin-Karp bump?
Answer
Verify equality on hash match.
Decode string?
Answer
Stack of counts + strings.
Calculator II?
Answer
Stack with last sign; * / pop apply.
Related wave-1?
Answer
sliding-window, stack, tries.
Z-algo?
Answer
Alternative O(n+m); less common in interviews than KMP intuition.
Repeated pattern via KMP?
Answer
p = n - lps[-1]; repeated iff lps[-1] > 0 and n % p == 0.