12. String Pattern Matching
KMP, Rabin-Karp and the Z-algorithm.
🎬 Episodes 18–19: video coming soon
Your progress0 of 7
2easy
1medium
4hard
Understand the topic
Finding a pattern inside a text the simple way restarts on every mismatch: O(n·m). Three classic algorithms avoid the restart.
KMP precomputes an LPS array (the longest proper prefix that is also a suffix) so a mismatch knows how far back to jump. Rabin-Karp compares rolling hashes of windows, and a hash match is then confirmed letter by letter. The Z-algorithm computes, for every position, how long a prefix of the string starts there.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Find the Index of the First Occurrence in a String #28 | KMP | Easy | LeetCode ↗ | |
| 2 | Repeated Substring Pattern #459 | Doubling trick / LPS | Easy | LeetCode ↗ | |
| 3 | Repeated String Match #686 | Repeat + KMP search | Medium | LeetCode ↗ | |
| 4 | Longest Happy Prefix #1392 | LPS array | Hard | LeetCode ↗ | |
| 5 | Shortest Palindrome #214 | KMP on s + # + reverse | Hard | LeetCode ↗ | |
| 6 | Longest Duplicate Substring #1044 | Binary search + Rabin-Karp | Hard | LeetCode ↗ | |
| 7 | Sum of Scores of Built Strings #2223 | Z-algorithm | Hard | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.