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.
The 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.
KMP 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.
The 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 |
In an interview
Write the naive version first and state its complexity. Then say what it wastes and how a prefix table removes that waste. Reaching for KMP immediately, without that framing, tends to read as memorisation.
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
| Problem | Pattern | Level |
|---|---|---|
| Implement indexOf / strStr | Naive or KMP | Easy |
| Repeated substring pattern | KMP prefix table | Medium |
| Shortest palindrome by prepending characters | KMP prefix table | Hard |
| Find all anagram start indices in a string | Sliding window + counts | Medium |
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 this topic solo, or share a room code and battle friends on it.
⚡ Start the Strings quiz