1Understand
The idea
Comparing the pattern at every position is O(n·m). KMP precomputes, for each prefix of the pattern, its longest proper prefix that is also a suffix, so after a mismatch it never re-reads text it has already matched (O(n + m)). Rolling hashes compare a window in O(1) by updating its hash as it slides.
Intuition
Comparing the pattern at every text position naively is O(n·m). KMP precomputes, for each prefix of the pattern, the longest proper prefix that is also a suffix, so after a mismatch you never re-read text you already matched, O(n + m).
Rolling hashes compare a window in O(1) after O(1) updates as the window slides; verify collisions if the problem demands certainty.
Reach for KMP or Rabin-Karp when n·m is too large under the constraints.
What you will be able to do
- Roll a hash in O(1)
- Verify matches to avoid false positives
When to use it
- Find a pattern in a long text
- Repeated substrings of length k
- Shortest palindrome / period of a string
2See it
Walkthrough
KMP scan with LPS
text = ababc, pattern = abc, j falls back on mismatch without rescanning text.
1 / 4
LPS for "abc" is [0,0,0]. i scans text, j scans pattern. Both start at 0.
Live template
Line 1 active
Complexity: time O(n + m), space O(m)
KMP O(n + m) time and O(m) space for π. Naive O(n·m). Rabin-Karp expected O(n + m) with good hashing; worst case degrades if you do not verify. Prefer naive when m is tiny.
Read the walkthrough as text
KMP idea on text `ababc`, pattern `abc`.
- LPS (π) for
abcis[0,0,0], no proper prefix equals a suffix until repeats exist (e.g.abab→[0,0,1,2]). - Scan text with pointer i, pattern with j. Match
a,b; at textavs patternc, mismatch. - j falls back via π (here to 0); continue. Eventually match
abcat index 2. - Total comparisons stay linear.
Rolling hash: hash of s[i:i+m] updates by removing s[i] and adding s[i+m] with powers of a base mod a prime.
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Rabin-Karp rolling hash
Example. Find pattern p in text t in expected O(n).
How. Roll hash over length-m windows; verify equality on hash match.
KMP prefix function
Example. Linear substring search with prefix table.
How. Build pi on pattern; on mismatch fall back j = pi[j-1].
Repeated substring pattern
Example. Is s built from repeating a smaller string?
How. KMP: full string matches prefix function at end (n - pi[n-1] divides n).
Longest duplicate substring (hash + binary search)
Example. Longest repeated substring in s.
How. Binary search length L; Rabin-Karp check if any hash repeats.
Shortest palindrome
Example. Add chars to front to make palindrome.
How. Find longest prefix that is suffix-palindrome via KMP on s + # + reverse(s).
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Hash collision ignored
Why it happens. Equal hash means equal string with high probability.
How it fails. Hash collision on "abc" vs "xyz" returns true without char compare, wrong index.
Fix. On hash match: verify pattern == text[i:i+m].
Slicing each step
Why it happens. Slice compare is the obvious Rabin-Karp check every step.
How it fails. O(n) slice per window → O(n·m) defeats rolling hash purpose.
Fix. Roll hash in O(1); slice only on hash hit.
Power recomputed
Why it happens. B**k each step is only one exponentiation.
How it fails. Recompute pow(B,k) or B**k inside the loop, extra log factor per window.
Fix. Precompute B^(k-1) mod M once; update remove term with stored power.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.