# String Algorithms

> Implement naive search, KMP (prefix function), Rabin-Karp (rolling hash), and DFA-based pattern matching in pure Python for exact substring/motif search in DNA or text. Use when finding restriction sites, scanning FASTQ/genome strings for a fixed motif, matching multiple same-length k-mers in one pass, or asked to explain/implement KMP failure function, rolling hash, or a pattern-matching automaton.

- Skill: `pavel-kravchenko/string-algorithms` (Agent Skill)
- Install (CLI): `npx skillmds@latest add pavel-kravchenko/string-algorithms`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pavel-kravchenko/string-algorithms/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: pavel-kravchenko (https://skillmd.com/u/pavel-kravchenko)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/pavel-kravchenko/string-algorithms

---


# String Matching Algorithms

## When to Use
- **Naive**: short patterns (m small), large alphabet, or one-off search; no setup cost
- **KMP**: guaranteed O(n+m), single pattern, repetitive pattern structure (e.g., ATATATG), streaming input
- **Rabin-Karp**: multiple patterns of the same length (hash all, scan once), plagiarism/duplicate detection
- **DFA**: small fixed alphabet (DNA: |Σ|=4), many texts against the same pattern, need O(1) per character with no backtracking
- Explaining/implementing the KMP failure function, rolling hash, or a pattern automaton from scratch

## Version Compatibility
Pure Python standard library only — no third-party dependencies. Works on Python ≥3.9 (uses `list[int]` built-in generics); drop the type hints for 3.8 or earlier.

## Prerequisites
- Comfortable with Python strings, lists, and dict indexing
- Basic Big-O intuition (the point of these algorithms is avoiding re-scanning text)
- No packages to install

## Quick Reference

| Algorithm | Preprocessing | Search | Space | Notes |
|-----------|--------------|--------|-------|-------|
| Naive     | O(1)         | O(n×m) | O(1)  | Best case O(n) with large alphabet |
| KMP       | O(m)         | O(n)   | O(m)  | Never backtracks in text |
| Rabin-Karp| O(m)         | O(n+m) avg, O(n×m) worst | O(1) | k patterns: O(n + k×m) |
| DFA       | O(m×\|Σ\|)   | O(n)   | O(m×\|Σ\|) | O(1) per char, no fallback logic |

## Naive and KMP Search

**Goal:** find every (possibly overlapping) occurrence of a single pattern in a text.
**Approach:** naive search brute-forces every start position; KMP precomputes a prefix (failure) function `sp[i]` — the length of the longest proper prefix of `pattern[0:i+1]` that is also a suffix — so on a mismatch the pattern pointer jumps back to `sp[j-1]` instead of restarting from 0.

```python
def naive_search(text: str, pattern: str) -> list[int]:
    """Return all start indices where pattern occurs in text (brute force)."""
    n, m = len(text), len(pattern)
    return [i for i in range(n - m + 1) if text[i:i + m] == pattern]


def prefix_function(p: str) -> list[int]:
    """KMP failure function: sp[i] = longest proper prefix of p[:i+1] that is also a suffix."""
    sp = [0] * len(p)
    j = 0
    for i in range(1, len(p)):
        while j >= 0 and p[j] != p[i]:
            j = sp[j - 1] if j - 1 >= 0 else -1
        j += 1
        sp[i] = j
    return sp


def kmp_search(text: str, pattern: str) -> list[int]:
    """Find all (including overlapping) occurrences of pattern in text in O(n+m)."""
    if not pattern or len(pattern) > len(text):
        return []
    matches = []
    f = prefix_function(pattern)
    n, m = len(text), len(pattern)
    j = 0
    for i in range(n):
        while j >= 0 and text[i] != pattern[j]:
            j = f[j - 1] if j - 1 >= 0 else -1
        j += 1
        if j == m:
            matches.append(i - m + 1)
            j = f[m - 1]  # allow overlapping matches, e.g. "AA" in "AAAA"
    return matches
```

## Rabin-Karp Rolling Hash

**Goal:** search one pattern, or many same-length patterns at once, using a hash instead of character comparison.
**Approach:** hash the pattern (and each same-length window of text) with a polynomial rolling hash `hash = (s[0]·b^(m-1) + s[1]·b^(m-2) + ... + s[m-1]) mod q`; sliding the window one position updates the hash in O(1) via `(base * (th - ord(text[i]) * h) + ord(text[i+m])) % mod`. A hash match is only a candidate — always verify with a direct string compare to rule out collisions.

```python
def rabin_karp_all(text: str, pattern: str, base: int = 256, mod: int = 1_000_000_007) -> list[int]:
    """Find all occurrences of pattern in text using a rolling hash, O(n+m) average."""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    h = pow(base, m - 1, mod)  # base^(m-1) mod q, precomputed once
    ph = th = 0
    for i in range(m):
        ph = (base * ph + ord(pattern[i])) % mod
        th = (base * th + ord(text[i])) % mod
    matches = []
    for i in range(n - m + 1):
        if th == ph and text[i:i + m] == pattern:  # verify to avoid spurious hash collisions
            matches.append(i)
        if i < n - m:
            th = (base * (th - ord(text[i]) * h) + ord(text[i + m])) % mod
    return matches


def rabin_karp_multi(text: str, patterns: list[str], base: int = 256, mod: int = 1_000_000_007) -> dict[str, list[int]]:
    """Search k same-length patterns (e.g. restriction enzyme sites) in a single pass over text."""
    if not patterns:
        return {}
    m = len(patterns[0])
    h = pow(base, m - 1, mod)
    pattern_hashes: dict[int, list[str]] = {}
    for p in patterns:
        ph = 0
        for c in p:
            ph = (base * ph + ord(c)) % mod
        pattern_hashes.setdefault(ph, []).append(p)
    results = {p: [] for p in patterns}
    th = 0
    for c in text[:m]:
        th = (base * th + ord(c)) % mod
    for i in range(len(text) - m + 1):
        if th in pattern_hashes:
            window = text[i:i + m]
            for p in pattern_hashes[th]:
                if window == p:
                    results[p].append(i)
        if i < len(text) - m:
            th = (base * (th - ord(text[i]) * h) + ord(text[i + m])) % mod
    return results
```

## DFA-Based Matching

**Goal:** search the same fixed pattern against many texts (e.g. millions of FASTQ reads) with O(1) work per character and no fallback logic.
**Approach:** build a transition table `automaton[state][char]` where `state` is how much of the pattern is matched so far; each transition is precomputed once via the KMP prefix trick (`prefix_length`), so scanning is a simple state-machine walk with no backtracking.

```python
def prefix_length(pattern: str, probe: str) -> int:
    """Longest prefix of pattern that is also a suffix of probe (KMP prefix-function trick)."""
    combined = pattern + "#" + probe + "$"
    sp = [0] * len(combined)
    j = 0
    for i in range(1, len(combined) - 1):
        while j > 0 and combined[i] != combined[j]:
            j = sp[j - 1]
        if combined[i] == combined[j]:
            j += 1
        sp[i] = j
    return sp[-2]  # value at the char right before the sentinel '$'


def build_automaton(pattern: str, alphabet: str) -> list[dict[str, int]]:
    """Build DFA transition table; state == len(pattern) is the accepting state."""
    return [
        {c: prefix_length(pattern, pattern[:i] + c) for c in alphabet}
        for i in range(len(pattern) + 1)
    ]


def dfa_search(text: str, automaton: list[dict[str, int]]) -> list[int]:
    """Scan text through the DFA; every char is O(1), no backtracking. Raises KeyError on out-of-alphabet chars."""
    accept = len(automaton) - 1
    state, matches = 0, []
    for i, c in enumerate(text):
        state = automaton[state][c]
        if state == accept:
            matches.append(i - accept + 1)
    return matches


alphabet = "ATGC"
pattern = "ATTCTGATTT"
dfa = build_automaton(pattern, alphabet)
hits = dfa_search("AATGCCGTATTCTATTCTGATTTCTGAATTCTGATTTTTAGT", dfa)  # -> [13, 27]
```

## Pitfalls

- **KMP overlapping matches**: after a full match, set `j = f[m-1]`, not `j = 0` — otherwise overlapping occurrences like `AA` in `AAAA` are missed.
- **Rabin-Karp spurious hits**: a hash match is not a guarantee; always verify with `text[i:i+m] == pattern`. Skip verification only if collision probability is provably negligible.
- **Rolling hash negative values**: `(th - ord(text[i]) * h) % mod` can go negative in Python — it wraps correctly, but in C/Java you must add `mod` before taking `%`.
- **DFA alphabet completeness**: every character in the text must have a transition defined; unrecognized characters raise `KeyError` — explicitly handle or restrict to the known alphabet (e.g. treat non-ACGT bases as mismatches).
- **DFA preprocessing cost**: O(m×|Σ|) build time — not worth it for |Σ|=256 (ASCII) with small `m`; prefer KMP there. It pays off for small fixed alphabets (DNA, |Σ|=4) reused across many texts.
- **Naive with `text[i:i+m]`**: creates a new string object per position (O(m) space each); use explicit char-by-char comparison for truly O(1) space.
- **KMP `j = -1` sentinel**: this implementation uses `j = -1` to signal "no prefix matched, advance without comparing" — don't confuse it with a real array index.

## Bioinformatics Connections

| Application | Algorithm | Notes |
|-------------|-----------|-------|
| Restriction site finding (EcoRI: `GAATTC`) | KMP or DFA | Single fixed pattern; DFA fast for streaming FASTQ |
| Motif scanning (TFBS, k-mer search) | Rabin-Karp | Hash all motif variants, single text pass |
| BLAST seed-and-extend | Naive | Short seed (11-mer default); large alphabet → fast mismatch |
| Tandem repeat detection | KMP prefix function | `sp[i]` reveals internal repetition period |
| Multiple restriction enzymes | Rabin-Karp multi | All enzymes same length → one scan |
| Long-read mapping seeds | DFA | Fixed seed pattern, millions of reads |

## See Also
- `graphs-dynamic-programming` — edit distance, Smith-Waterman use DP on character grids
- `advanced-string-structures` — tries, Aho-Corasick, and suffix arrays for many-pattern or all-substring queries
- `algo-suffix-arrays` — O(n log n) suffix array + Kasai LCP for repeated-motif and k-mer counting
- `algo-hash-tables-bloom` — hash table / Bloom filter internals underlying the Rabin-Karp hash