AdvancedData Structures & Algorithms · Lesson 37 of 40 · Updated ·
String Matching — Naive Search, KMP and Rabin-Karp
String matching means finding every position where a short string, the pattern (length m), appears inside a longer string, the text (length n). Your editor's "Find" box, plagiarism checkers and DNA search tools all do this. Languages already have text.find() in Python and indexOf() in Java, and in real code you should use them. Interviewers still ask how to search efficiently, because the ideas behind KMP and Rabin-Karp — reusing work you already did — show up in many other problems.
1. Naive search
Try every starting position i and compare the pattern letter by letter.
def naive_search(text, pat):
n, m = len(text), len(pat)
found, comparisons = [], 0
for i in range(n - m + 1):
j = 0
while j < m:
comparisons += 1
if text[i + j] != pat[j]:
break
j += 1
if j == m:
found.append(i)
return found, comparisons
print(naive_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(naive_search("A" * 20, "AAAB"))
([10], 29)
([], 68)
The second line is the bad case. At every position the first three A's match and only the B fails, so almost every letter of the text is compared m times. In the worst case the work is O(n · m). With a text of 10⁶ letters and a pattern of 10³, that is up to 10⁹ comparisons.
The waste: after matching "AAA" at position 0, the naive method moves to position 1 and compares "AA" again, even though it already knows those letters are A.
2. The KMP idea: the prefix table
KMP (Knuth–Morris–Pratt) never moves backwards in the text. When a mismatch happens after j letters matched, it asks: "how much of what I just matched can still be the start of the pattern?" That answer is stored for every position of the pattern in the LPS array.
lps[i] = length of the longest proper prefix of pat[0..i] that is also a suffix of it. ("Proper" means not the whole string.)
For example, pat[0..3] is "ABAB". Its prefix "AB" is also its suffix, so lps[3] = 2. If a mismatch happens right after matching "ABAB", we know the last two letters of the text are "AB" — exactly the first two letters of the pattern — so we continue from j = 2 instead of starting over.
Building the table uses the same trick on the pattern itself:
def build_lps(p):
lps = [0] * len(p)
k = 0 # length of the current matching prefix
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = lps[k - 1] # fall back to a shorter prefix
if p[i] == p[k]:
k += 1
lps[i] = k
return lps
print(build_lps("ABABCABAB"))
print(build_lps("AAAA"))
print(build_lps("ABCD"))
[0, 0, 1, 2, 0, 1, 2, 3, 4]
[0, 1, 2, 3]
[0, 0, 0, 0]
3. KMP search
The search loop is almost the same as building the table. j is how many pattern letters currently match.
def build_lps(p):
lps, k = [0] * len(p), 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = lps[k - 1]
if p[i] == p[k]:
k += 1
lps[i] = k
return lps
def kmp_search(text, pat):
lps, j, found = build_lps(pat), 0, []
for i, ch in enumerate(text):
while j > 0 and ch != pat[j]:
j = lps[j - 1] # keep the part that can still match
if ch == pat[j]:
j += 1
if j == len(pat): # full match ends at i
found.append(i - len(pat) + 1)
j = lps[j - 1] # allow overlapping matches
return found
print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
print(kmp_search("AAAAA", "AA"))
print(kmp_search("placement preparation", "pa"))
[10]
[0, 1, 2, 3]
[13]
"AA" in "AAAAA" is found 4 times, at 0, 1, 2 and 3, because matches may overlap.
Why it is O(n + m). In the search loop, i only moves forward. j goes up by at most 1 per letter, and every while step makes j smaller, so the total number of fall-backs cannot exceed the total number of increases, which is at most n. The LPS table costs O(m) by the same argument.
The same in Java:
public class Main {
static int[] lps(String p) {
int[] t = new int[p.length()];
for (int i = 1, k = 0; i < p.length(); i++) {
while (k > 0 && p.charAt(i) != p.charAt(k)) k = t[k - 1];
if (p.charAt(i) == p.charAt(k)) k++;
t[i] = k;
}
return t;
}
static int countMatches(String text, String pat) {
int[] t = lps(pat);
int j = 0, count = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pat.charAt(j)) j = t[j - 1];
if (text.charAt(i) == pat.charAt(j)) j++;
if (j == pat.length()) { count++; j = t[j - 1]; }
}
return count;
}
public static void main(String[] args) {
System.out.println(countMatches("abababab", "abab"));
System.out.println(countMatches("hello world", "o"));
System.out.println(countMatches("aaaa", "b"));
}
}
3
2
0
4. Rabin-Karp: compare numbers, not strings
Rabin-Karp turns each window of m letters into a number called a hash, and compares numbers instead of letters. The trick is the rolling hash: the next window's hash is computed from the previous one in O(1), by removing the first letter and adding the new one.
The picture uses digits so the hash is simply the number itself:
For letters, treat the string as a number in base B (for example 256) and keep it small with % MOD (a large prime). Different strings can then get the same hash — a collision — so when the hashes are equal we still compare the actual letters.
def rabin_karp(text, pat, B=256, MOD=1_000_000_007):
n, m = len(text), len(pat)
if m > n:
return []
high = pow(B, m - 1, MOD) # weight of the first letter
hp = hw = 0
for k in range(m):
hp = (hp * B + ord(pat[k])) % MOD
hw = (hw * B + ord(text[k])) % MOD
found = []
for i in range(n - m + 1):
if hw == hp and text[i:i + m] == pat: # check: hashes can collide
found.append(i)
if i + m < n: # roll to the next window
hw = ((hw - ord(text[i]) * high) * B + ord(text[i + m])) % MOD
return found
print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB"))
print(rabin_karp("the cat sat on the mat", "at"))
[10]
[5, 9, 20]
Expected time is O(n + m); with many collisions it can degrade to O(n · m), which a good prime modulus makes very unlikely. Rabin-Karp shines when you search for many patterns of the same length at once (put their hashes in a set), or when comparing substrings quickly, as in "longest repeated substring" with binary search.
5. Which one to use?
| Method | Time | Best for |
|---|---|---|
Built-in find / indexOf | fast in practice | everyday code |
| Naive | O(n · m) worst | very short patterns, quick scripts |
| KMP | O(n + m) always | guaranteed speed, period and border problems |
| Rabin-Karp | O(n + m) expected | many patterns of one length, substring hashing |
The LPS table is useful on its own. For instance, a string of length n is made of a repeated block (like "abcabcabc") exactly when p = n − lps[n − 1] divides n and p < n; the block is the first p letters.
Common mistakes
- Thinking
lps[i]may be the whole string — it is the longest proper prefix, solps[0]is always 0. - Resetting
jto 0 on a mismatch instead of falling back tolps[j − 1]. - Forgetting
j = lps[j − 1]after a full match, which misses overlapping matches or reads past the pattern. - In Rabin-Karp, trusting equal hashes without comparing the letters.
- Getting a negative hash in Java or C++ after subtracting; add
MODbefore taking%again. (Python's%is never negative for a positiveMOD.)
Quick recap
- Naive search: O(n · m) worst case, because it re-compares letters it already saw.
- LPS: longest proper prefix of
pat[0..i]that is also a suffix. - KMP: on a mismatch, fall back to
lps[j − 1]; the text pointer never moves back; O(n + m). - Rabin-Karp: rolling hash, O(1) per window, verify on equal hashes; O(n + m) expected.
- In real code use the built-in search; know KMP and Rabin-Karp for interviews.