Skills101

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.

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.)

LPS table for the pattern ABABCABAB: the values are 0 0 1 2 0 1 2 3 4; the last value 4 means ABAB is both the start and the end of the pattern

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]

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:

Rolling hash search for 592 in the digits 31415926535: each 3-digit window value is computed from the previous one by dropping the first digit and adding the next, and the window starting at index 4 has value 592, a match

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?

MethodTimeBest for
Built-in find / indexOffast in practiceeveryday code
NaiveO(n · m) worstvery short patterns, quick scripts
KMPO(n + m) alwaysguaranteed speed, period and border problems
Rabin-KarpO(n + m) expectedmany 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, so lps[0] is always 0.
  • Resetting j to 0 on a mismatch instead of falling back to lps[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 MOD before taking % again. (Python's % is never negative for a positive MOD.)

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.

Practice what you learned

📝 Quiz: String Matching — KMP and Rabin-Karp5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →