What is Pattern Matching?
Pattern matching finds where a smaller sequence occurs inside a larger sequence. The interesting algorithms avoid restarting from zero after every mismatch.
You need string indexes, prefixes, suffixes, and basic hashing for the hash-based variant. The short version is: remember what the matched prefix already tells you, then continue from the earliest position that could still work.
The Core Idea: Reuse the Match
In LC 28: KMP Search, the text is ababcababd and the pattern is ababd.
The first four pattern characters can match before the final character fails.
Do we need to compare those four characters from scratch at the next text position? No. The matched text ends with characters that are also a prefix of the pattern, so KMP keeps that smaller match and continues.
It is like aligning two transparent strips with repeated marks. After a mismatch, you slide the pattern only far enough to line up the repeated marks that already agree.
How KMP Handles a Mismatch
The Rule You Keep True
Before each KMP comparison, the first j pattern characters match the text ending immediately before i.
An LPS fallback keeps the largest smaller prefix for which that statement remains true.
The reuse strategy changes by algorithm:
- KMP reuses prefix and suffix structure after a mismatch.
- Rabin-Karp reuses most of the previous window's hash.
- Wildcard matching reuses answers for text and pattern position pairs.
LC 28: Build LPS Array is the one that usually trips us up. When two pattern characters fail to match, the candidate prefix length falls back through an earlier LPS value rather than always returning straight to zero.
Picking the Right Shape
From Rule to Code
- Choose whether the reusable information is an LPS table, rolling hash, or DP state.
- Build any pattern-only preprocessing before scanning the text.
- Compare the current text and pattern positions.
- Advance on a match or use the stored information to skip impossible alignments.
- Return when the full pattern matches or every possible alignment is exhausted.
KMP scans the pattern and text in O(m + n) time with O(m) space for the LPS table.
When to use it
- •You need to find a pattern inside a larger text.
- •A mismatch should reuse information from earlier matched characters.
- •Many text windows must be compared without rereading each one from the beginning.
- •The pattern contains wildcard characters with special matching rules.
How to identify it
- •The prompt provides a text and a smaller pattern.
- •A brute-force solution restarts the pattern after every mismatch.
- •Repeated prefixes or suffixes can tell the search where to continue.
- •The expected solution names KMP, rolling hash, Rabin-Karp, or wildcard matching.
Key insights
- →KMP stores how much of the pattern is still useful after a mismatch.
- →The LPS value at one pattern index is the length of the longest proper prefix that is also a suffix there.
- →Rabin-Karp compares rolling hashes before checking characters directly.
- →Hash matches must still be verified because different strings can share a hash.
- →Wildcard matching needs state that records positions in both the text and pattern.
Common mistakes
- 01Resetting the text pointer after a KMP mismatch and losing the saved work.
- 02Building the LPS array from the text instead of the pattern.
- 03Treating the full pattern as a proper prefix of itself.
- 04Accepting equal rolling hashes without checking for a collision.
- 05Treating `*` like `?` even though `*` may match several characters or none.