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

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.

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.

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.

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

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