# String Matching — Naive Search, KMP and Rabin-Karp

Source: https://skills101.in/learn/dsa/dsa-string-matching-kmp-rabin-karp — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

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

```python
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"))
```

```text
([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](https://skills101.in/learn-img/dsa/kmp-lps.svg)

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:

```python
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"))
```

```text
[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.

```python
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"))
```

```text
[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:

```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"));
    }
}
```

```text
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](https://skills101.in/learn-img/dsa/rabin-karp.svg)

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.

```python
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"))
```

```text
[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, 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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-string-matching-kmp-rabin-karp