Course contents
String Pattern Matching: Naive Search and KMP
Finding a pattern inside a text is the most-used string operation there is, and the naive approach throws away information on every mismatch. KMP is the classic fix: precompute what the pattern already told you about itself, so the search never rechecks the same character twice.
01The naive scan
int naiveSearch(String text, String pattern) {
int n = text.length(), m = pattern.length();
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
if (j == m) return i; // full match at i
}
return -1;
}Worst case O(n x m) — text "aaaaaaaab" against pattern "aaab" nearly matches at every position and fails on the last character each time. In practice it is often fine; in an interview it is the baseline you improve on.
02KMP and the prefix table
The naive version restarts the pattern from scratch after a mismatch. But the characters that already matched are known — and if the pattern's start reappears inside that matched region, part of the work is still valid. The prefix table (also called the failure function or LPS array) records exactly that: for each position, the length of the longest proper prefix that is also a suffix.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Character | a | b | a | b | a | c | a |
| LPS | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
int[] buildLps(String p) {
int[] lps = new int[p.length()];
int len = 0;
for (int i = 1; i < p.length(); ) {
if (p.charAt(i) == p.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1]; // fall back, do not restart
} else {
lps[i++] = 0;
}
}
return lps;
}
int kmpSearch(String text, String pattern) {
int[] lps = buildLps(pattern);
int i = 0, j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == pattern.length()) return i - j;
} else if (j > 0) {
j = lps[j - 1]; // reuse the matched prefix
} else {
i++;
}
}
return -1;
}The text index i never moves backwards, so the search is O(n); building the table is O(m). O(n + m) total, O(m) space — and the reason it works is that the pattern's overlap with itself was computed before the search started.
03The other algorithms, and when they matter
| Algorithm | Time | Best for |
|---|---|---|
| Naive | O(n x m) | Short patterns; readable code |
| KMP | O(n + m) | Guaranteed linear worst case |
| Rabin-Karp | O(n + m) average | Searching for many patterns at once |
| Boyer-Moore | Sublinear in practice | Long patterns over long text; what grep uses |
| Built-in indexOf / find | Implementation-defined | Real production code |
Key takeaways
- Naive search is O(n x m) because it rechecks characters it already matched.
- The prefix table stores, per position, the longest proper prefix that is also a suffix.
- KMP never moves the text index backwards: O(n + m) time, O(m) space.
- Rabin-Karp suits many patterns; Boyer-Moore is fastest in practice on long text.
Practice problems
Tagged by pattern, so you can tell whether you learned the idea or just the example.
- Implement indexOf / strStrNaive or KMPEasy
- Repeated substring patternKMP prefix tableMedium
- Shortest palindrome by prepending charactersKMP prefix tableHard
- Find all anagram start indices in a stringSliding window + countsMedium
Frequently asked questions
What is the KMP algorithm?
Knuth-Morris-Pratt is a substring search that precomputes a prefix table for the pattern, so that after a mismatch it can skip ahead using what already matched instead of restarting. It runs in O(n + m).
What is the LPS array in KMP?
For every position in the pattern it stores the length of the longest proper prefix of the pattern that is also a suffix ending at that position. That value is how far the pattern can shift without missing a match.
Is KMP always faster than the naive approach?
It is better in the worst case, but the naive scan is often faster on short patterns and random text because it has no setup cost and better cache behaviour. KMP's value is the guarantee.
Test yourself on Strings
Reading is not recall. Take a timed quiz on Strings solo, or share a room code and battle friends on it.