| name | algo-dfa-matching |
| description | Build a DFA transition table via the KMP prefix function, then scan text in O(n) with zero backtracking. Use when repeatedly searching one fixed pattern (motif, restriction site, primer) against many sequences or texts. |
| tool_type | python |
| primary_tool | Python |
DFA-Based Pattern Matching
When to Use
- Searching the same fixed pattern (a motif, restriction site, primer, or start codon) against many different texts/sequences — build the DFA once, reuse it everywhere.
- You need a hard guarantee of no backtracking on the text pointer (streaming/online matching, where re-reading input isn't possible).
- Teaching/explaining why KMP works — the DFA is the "unrolled" state machine that the KMP failure-link trick simulates lazily.
- The alphabet is small and fixed (DNA:
ACGT, protein: 20 letters) so the O(m·|Σ|) build cost is cheap.
- Not the right tool for: searching many different patterns against one text (use
algo-aho-corasick), or a huge/unbounded alphabet (use KMP instead, see algo-kmp-algorithm).
Version Compatibility
Pure Python standard library only — no third-party dependencies. Works unchanged on Python ≥ 3.8 (uses only list/dict and str slicing; the list[int] / dict[int, dict[str, int]] type hints require Python ≥ 3.9 or from __future__ import annotations on 3.8).
Prerequisites
- No packages to install.
- Prior concept: the KMP prefix (failure) function — see
algo-kmp-algorithm — since build_dfa reuses it to compute fallback transitions.
How It Works
Build a DFA with m+1 states where state i = "matched the first i characters of the pattern". State m is accepting. The transition function δ(state, char) gives the length of the longest prefix of the pattern that is a suffix of pattern[:state] + char.
vs KMP
| DFA | KMP |
|---|
| Build | O(m·|Σ|) | O(m) |
| Search | O(n) | O(n) |
| Space | O(m·|Σ|) | O(m) |
| Backtracking | None (table lookup) | Via failure links |
| Multi-text reuse | Ideal (precomputed table) | Rebuild failure links per pattern (cheap, but still work) |
Use DFA when you search one pattern against many texts and want table-lookup speed. Use KMP to save memory or when you only search once.
Goal: find every (possibly overlapping) occurrence of pattern in text with a single linear pass and no re-reading of text.
Approach: compute the KMP prefix function once, use it to fill in a full state × alphabet transition table, then drive the search with pure table lookups.
def compute_prefix_function(pattern: str) -> list[int]:
"""KMP prefix (failure) function: pi[i] = length of the longest proper
prefix of pattern[:i+1] that is also a suffix of it."""
m = len(pattern)
pi = [0] * m
k = 0
for i in range(1, m):
while k > 0 and pattern[i] != pattern[k]:
k = pi[k - 1]
if pattern[i] == pattern[k]:
k += 1
pi[i] = k
return pi
def build_dfa(pattern: str, alphabet: str) -> dict[int, dict[str, int]]:
"""Build the DFA transition table for exact matching of `pattern`.
dfa[state][ch] = next state after reading `ch` while in `state`.
Time/space: O(m * |alphabet|).
"""
m = len(pattern)
pi = compute_prefix_function(pattern)
dfa: dict[int, dict[str, int]] = {}
for state in range(m + 1):
dfa[state] = {}
for ch in alphabet:
if state < m and ch == pattern[state]:
dfa[state][ch] = state + 1
else:
k = state
while k > 0:
k = pi[k - 1]
if k < m and ch == pattern[k]:
k += 1
break
if k == 0:
k = 1 if ch == pattern[0] else 0
break
dfa[state][ch] = k
return dfa
def dfa_search(text: str, pattern: str, alphabet: str) -> list[int]:
"""Return 0-based start positions of every (possibly overlapping)
occurrence of `pattern` in `text` using a precomputed DFA."""
if not pattern:
return []
m = len(pattern)
dfa = build_dfa(pattern, alphabet)
state = 0
results = []
for i, ch in enumerate(text):
state = dfa[state].get(ch, 0)
if state == m:
results.append(i - m + 1)
return results
Goal: amortize the DFA build cost by reusing it across many texts (e.g. scanning a restriction-site motif against thousands of reads).
Approach: build once, then call a lightweight scan function per text.
def scan_many(texts: list[str], pattern: str, alphabet: str) -> dict[str, list[int]]:
"""Search `pattern` across multiple `texts`, building the DFA only once.
Returns a dict mapping each text to its list of match start positions.
"""
dfa = build_dfa(pattern, alphabet)
m = len(pattern)
hits: dict[str, list[int]] = {}
for text in texts:
state = 0
positions = []
for i, ch in enumerate(text):
state = dfa[state].get(ch, 0)
if state == m:
positions.append(i - m + 1)
hits[text] = positions
return hits
Example
Pattern: "ABABC" Text: "ABABABC"
State: 0→1→2→3→4→3→4→5
↑
δ(4,'A')=3 (fell back; "ABAB"+"A" → suffix "ABA" = pattern[:3])
Match at position 2: text[2:7] = "ABABC"
Pitfalls
- Alphabet must cover all text characters: characters not in
alphabet get no entry in dfa[state]; handle via .get(ch, 0) or enumerate the actual text to build the alphabet.
- Build is O(m × |Σ|), not O(m): for large alphabets (Unicode), this is expensive — prefer KMP or Aho-Corasick.
- State m is accepting but search continues: after reaching state m, the DFA naturally transitions to the correct fallback state to find overlapping matches — do not reset to 0.
- Empty pattern edge case:
m=0 means every position matches; handle before building the DFA.
- Fallback loop in build: the while loop mirrors KMP's failure-link traversal; an off-by-one in the
pi index (pi[k-1] vs pi[k]) silently produces wrong transitions.
- Rebuilding per text wastes the whole point of DFA: if you find yourself calling
build_dfa inside a loop over texts, switch to scan_many-style reuse or just use plain KMP.
See Also
algo-kmp-algorithm — the failure-function algorithm this DFA is built from; use it instead when memory matters or you search only once.algo-aho-corasick — multi-pattern generalization of this same automaton idea.bio-restriction-analysis-restriction-sites — applies fixed-motif scanning like this to restriction enzyme recognition sites.bio-sequence-manipulation-motif-search — higher-level motif search over Seq objects, often backed by exactly this kind of automaton.
