String Matching (KMP / Z / Rabin-Karp)
Precompute how much of the pattern is reusable after a mismatch so the text pointer never moves backwards.
StringsO(n + m)New7 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
find a pattern in text
repeated substring
shortest palindrome
The template
Get this into muscle memory, then adapt the condition per problem.
// LPS: longest proper prefix which is also a suffix
const lps = new Array(m).fill(0);
for (let i = 1, len = 0; i < m; ) {
if (p[i] === p[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
} Watch KMP Pattern MatchingIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Naive matching rescans the text after each mismatch.
- 2After a partial match you already know some of the next characters.
- 3The prefix function tells you how far to fall back.
Drill it
Every problem in the bank that uses this pattern.
0 / 7 solved