DFA-Based Pattern Matching
How It Works
Build a DFA with m+1 states where state i = "matched first i chars of pattern". Accepting state = m. Transition function: δ(state, char) = longest prefix of 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) |
[Description truncada. Veja o README completo no GitHub.]