# String Matching — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/string-matching

> Finding a pattern inside text efficiently — KMP's failure function and a glance at Rabin-Karp hashing.

## Why not brute force?

Naively sliding the pattern across the text and comparing is `O(n*m)`. **KMP (Knuth-Morris-Pratt)** avoids re-checking characters it already matched by precomputing, for the pattern, how far to fall back on a mismatch — giving `O(n + m)`.

## KMP failure function

`lps[i]` stores the length of the longest proper prefix of `pattern[0..i]` that is also a suffix — this tells KMP how far to shift on a mismatch instead of restarting.

```python
def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    lps = build_lps(pattern)
    matches, i, j = [], 0, 0
    while i < len(text):
        if text[i] == pattern[j]:
            i, j = i + 1, j + 1
            if j == len(pattern):
                matches.append(i - j)
                j = lps[j - 1]
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return matches
```

Output:

```
kmp_search('ababcabab', 'abab')  # [0, 5]
```

## Rabin-Karp at a glance

**Rabin-Karp** hashes the pattern and every window of the text, comparing hashes first (`O(1)` via a **rolling hash**) and only verifying character-by-character on a hash match. Great for searching **many patterns at once**.

## Quick check

Test KMP's complexity.

**Quiz:** KMP's overall time complexity for searching pattern of length m in text of length n is:

- [ ] O(n*m)
- [x] O(n + m)
- [ ] O(n log m)
- [ ] O(m^2)

*Answer:* O(n + m). The LPS array is built in O(m), and the search itself is O(n) since the text pointer never backtracks.