Finite Automata String Matching: Complete Implementation Guide

1. Introduction and Core Concepts

Finite Automata string matching is one of the most elegant applications of automata theory to practical algorithm design. At its core, it transforms the problem of finding a pattern inside a text into the problem of simulating a Deterministic Finite Automaton (DFA) that has been specially constructed to recognize that pattern. Instead of repeatedly comparing characters and backtracking upon mismatches, the automaton processes the text in a single left-to-right pass, transitioning between states based solely on the next input character.

A finite automaton for string matching is defined by a 5-tuple (Q, Σ, δ, q0, F) where Q is the set of states, Σ is the alphabet, δ is the transition function, q0 is the start state, and F is the set of accepting states. For a pattern P of length m, we create m+1 states numbered 0 to m. State k represents that the longest prefix of P that is a suffix of the text processed so far has length k. State 0 is the initial state meaning no prefix matched, and state m is the unique accepting state indicating that the entire pattern has been found.

Why does this matter? Traditional naive string matching can degrade to O((n-m+1) * m) time when many partial matches occur, which is unacceptable for large-scale systems processing gigabytes of logs, network packets, or genomic data. The finite automata approach guarantees linear-time scanning of the text after a one-time preprocessing phase. Its deterministic, constant-time per character behavior makes it highly predictable, cache-friendly, and ideal for hardware implementation, real-time systems, and streaming data where backtracking is impossible. Understanding this method also provides the theoretical foundation for more advanced algorithms like Knuth-Morris-Pratt (KMP) and Aho-Corasick.

Key Terminology

The alphabet Σ is the set of all possible characters that can appear. For ASCII text, |Σ| = 256; for DNA sequences, |Σ| = 4 (A, C, G, T). The transition function δ(q, a) defines the next state when the automaton is in state q and reads character a. The computation of δ is the preprocessing step and encodes all knowledge about the pattern's structure, including its internal overlaps and borders. This preprocessing allows the matching phase to be completely oblivious to the pattern itself.

Another crucial concept is the suffix-prefix overlap. When a mismatch occurs, we do not need to restart from the beginning. The automaton knows the longest prefix of the pattern that is also a suffix of what has been matched so far. For example, if the pattern is "ABABC" and we have matched "ABAB" and the next character is not "C", the automaton knows that the suffix "AB" of "ABAB" is also a prefix of "ABABC", so it can transition to state 2 instead of state 0.

2. How It Works

The mechanism of finite automata string matching consists of two distinct phases: automaton construction and text scanning. During construction, we build a complete transition table of size (m+1) × |Σ|. Each entry δ[q][c] answers the question: if we have matched the first q characters of the pattern and the next text character is c, what is the length of the longest prefix of P that is a suffix of the matched portion plus c?

Formally, δ(q, a) = max { k | k ≤ min(m, q+1) and Pk is a suffix of (Pq + a) }, where Pk denotes the prefix of P of length k and Pq + a is the string consisting of the first q characters of P followed by character a. This definition ensures that no potential match is missed. The automaton essentially remembers the relevant history of the text in its state, which is the most valuable information needed to continue the search without re-examining characters.

Once the automaton is built, the matching phase is trivial. We start in state 0 and iterate over the text T of length n. For each character T[i], we update state = δ(state, T[i]). If state becomes m, we have found an occurrence ending at position i. We then continue scanning, which automatically allows detection of overlapping occurrences. Because each character causes exactly one table lookup and state update, the scanning is strictly O(n).

The Transition Function Intuition

Think of the automaton as a very smart pattern memory. State q means you are q characters deep into the pattern. If the next character matches P[q], you advance to q+1. If it does not match, you do not fall back to zero immediately. Instead, you fall back to the state that corresponds to the longest border of the string you have seen. This is similar to how humans search: if you are looking for "ababa" and you see "ababx", you realize the last "ab" could be the start of a new match.

The naive method to compute δ tries all possible k values for each state and alphabet symbol, checking if Pk is a suffix of Pq + a. While correct, this takes O(m³ × |Σ|) time. More efficient constructions use the prefix function (also called failure function) from KMP to compute δ in O(m × |Σ|) time, which is crucial when m and |Σ| are large.

Determinism and Completeness

The automaton is deterministic and complete: for every state and every alphabet character, there is exactly one defined transition. This completeness eliminates the need for failure transitions during scanning and guarantees O(1) per character. In contrast, the KMP automaton is not complete and requires a while-loop to follow failure links, though it saves space. The trade-off is time predictability versus memory usage.

3. Implementation

Implementing finite automata string matching in Python requires careful handling of the alphabet and the transition table. For general-purpose text, we can either build a full 2D list for a fixed alphabet or use a dictionary-based transition table for sparse or large alphabets (like Unicode). Below are complete, production-ready implementations with detailed comments.

Naive Transition Table Construction

This first implementation is the most didactic. It directly implements the formal definition of δ and is ideal for learning and for small patterns and alphabets.

def compute_transition_function_naive(pattern, alphabet):
    """
    Compute DFA transition function using the naive O(m^3 * |Sigma|) method.
    Returns a dict: delta[state][char] -> next_state
    """
    m = len(pattern)
    delta = {q: {} for q in range(m + 1)}

    for q in range(m + 1):
        for a in alphabet:
            # k is the candidate next state, from largest to smallest
            # We want the largest k such that P_k is suffix of (P_q + a)
            # P_q is pattern[0:q]
            prefix_q_plus_a = pattern[:q] + a
            # k cannot exceed m and cannot exceed len(prefix_q_plus_a)
            max_k = min(m, q + 1)
            for k in range(max_k, -1, -1):
                # Check if pattern[:k] is suffix of prefix_q_plus_a
                if prefix_q_plus_a.endswith(pattern[:k]):
                    delta[q][a] = k
                    break
    return delta

Efficient Construction Using Prefix Function

For larger patterns, the naive method is too slow. This optimized version uses the prefix function pi (longest proper prefix which is also suffix) to compute transitions in O(m * |Σ|). This is the approach used in practice and is essentially how KMP builds its automaton.

def compute_prefix_function(pattern):
    """Compute KMP prefix function pi for pattern."""
    m = len(pattern)
    pi = [0] * m
    k = 0
    for q in range(1, m):
        while k > 0 and pattern[k] != pattern[q]:
            k = pi[k - 1]
        if pattern[k] == pattern[q]:
            k += 1
        pi[q] = k
    return pi

def compute_transition_function_efficient(pattern, alphabet):
    """
    Efficient O(m * |Sigma|) construction of DFA.
    Uses prefix function to avoid re-scanning.
    """
    m = len(pattern)
    pi = compute_prefix_function(pattern) if m > 0 else []
    delta = {q: {} for q in range(m + 1)}

    for q in range(m + 1):
        for a in alphabet:
            if q < m and a == pattern[q]:
                # Direct match, advance
                delta[q][a] = q + 1
            else:
                if q == 0:
                    delta[q][a] = 0
                else:
                    # Fall back using prefix function and reuse computed transition
                    # delta[q][a] = delta[pi[q-1]][a]
                    fallback_state = pi[q - 1]
                    delta[q][a] = delta[fallback_state][a]
    return delta

The Matching Engine

Once the transition table is built, scanning is extremely simple and fast. The matcher is a pure DFA simulation.

def finite_automata_matcher(text, pattern, alphabet=None):
    """
    Search for pattern in text using finite automata.
    Returns list of starting indices where pattern occurs.
    """
    m = len(pattern)
    n = len(text)

    if m == 0:
        return list(range(n + 1))
    if alphabet is None:
        # Infer alphabet from pattern + text for dictionary-based delta
        alphabet = set(pattern) | set(text)

    delta = compute_transition_function_efficient(pattern, alphabet)

    state = 0
    occurrences = []

    for i in range(n):
        char = text[i]
        # If char not in alphabet, transition to 0 (or handle via default)
        if char in delta[state]:
            state = delta[state][char]
        else:
            # For characters outside alphabet, fallback to 0
            # In a full table this would be precomputed
            state = 0
            # Check if char equals pattern[0] for potential start
            if char == pattern[0]:
                state = 1

        if state == m:
            # Match ending at i, starting at i - m + 1
            occurrences.append(i - m + 1)

    return occurrences

Complete Driver with Dictionary Optimization for Large Alphabets

When Σ is large (e.g., Unicode), a full table is wasteful. We can store only non-zero transitions and default to 0. This version is memory-efficient for natural language processing.

def build_sparse_dfa(pattern):
    """
    Build sparse DFA using dict for transitions.
    Only stores transitions that are not self-loops to 0.
    Ideal for large alphabets.
    """
    m = len(pattern)
    delta = [{} for _ in range(m + 1)]
    pi = compute_prefix_function(pattern) if m > 0 else []

    # Pre-fill direct matches
    for q in range(m):
        delta[q][pattern[q]] = q + 1

    # Fill fallback transitions
    for q in range(1, m + 1):
        for char, next_state in delta[pi[q - 1]].items():
            if char not in delta[q]:
                delta[q][char] = next_state
        # Ensure missing transitions implicitly go to 0
    return delta

def sparse_fa_search(text, pattern):
    """Search using sparse DFA representation."""
    if not pattern:
        return []
    m = len(pattern)
    delta = build_sparse_dfa(pattern)
    state = 0
    result = []
    for i, ch in enumerate(text):
        # Get transition, default 0 if not found
        state = delta[state].get(ch, 0)
        # Special handling: if state is 0 and ch == pattern[0], we should be in 1
        # But our sparse construction already handles this via fallback
        if state == m:
            result.append(i - m + 1)
            # Allow overlapping matches by following pi
            # State remains m, next iteration will use delta[m]
    return result

# Example usage:
# text = "ABABABACABA"
# pattern = "ABABAC"
# print(sparse_fa_search(text, pattern))  # -> [2]

4. Step-by-Step Example

Let us walk through a concrete example to make the abstract transition function tangible. Choose pattern P = "ABA" with alphabet Σ = {A, B, C}. The pattern length m = 3, so we will have states 0, 1, 2, 3. State 3 is the accepting state. We will construct the full transition table δ.

We compute each entry by asking for the longest prefix of "ABA" that is a suffix of (Pq + a). For instance, consider state q=1 (we have matched "A") and input a="B". Pq + a = "A" + "B" = "AB". The longest prefix of "ABA" that is a suffix of "AB" is "AB" itself (length 2), so δ(1, B) = 2. Now consider q=2 (matched "AB") and a="A". Pq + a = "AB" + "A" = "ABA". The longest prefix of "ABA" that is a suffix of "ABA" is "ABA" (length 3), so δ(2, A) = 3. This is the accepting transition.

A more interesting case is a mismatch that does not reset to zero. Consider q=2 (matched "AB") and a="B". Pq + a = "ABB". What is the longest prefix of "ABA" that is a suffix of "ABB"? Check k=3: "ABA" != suffix "ABB". k=2: "AB" != "BB". k=1: "A" != "B". k=0: "" is always a suffix. So δ(2, B) = 0. But consider pattern "ABAB" and state q=3 with a="A" – there the fallback would be to state 1 or 2, not 0. This demonstrates how the automaton preserves overlap information.

Complete Transition Table for P = "ABA"

Notice the last row: after accepting "ABA", if the next character is "B", we go to state 2, not 0. Why? Because the suffix "AB" of "ABAB" (which is "ABA" + "B") is also a prefix of "ABA"? Wait, check: "ABAB" suffix of length 2 is "AB", which equals P2. So the automaton correctly prepares for an overlapping occurrence like "ABABA" where two occurrences overlap. This is a key advantage over naive search that would miss overlaps if it simply resets.

Scanning Text T = "ABABACABA"

Let us simulate scanning. Start at state 0.

• i=0, T[0]=A: δ(0,A)=1 → state=1
• i=1, T[1]=B: δ(1,B)=2 → state=2
• i=2, T[2]=A: δ(2,A)=3 → state=3 → Match at 0 (0 = 2-3+1)
• i=3, T[3]=B: δ(3,B)=2 → state=2 (overlap handling)
• i=4, T[4]=A: δ(2,A)=3 → state=3 → Match at 2 (2 = 4-3+1)
• i=5, T[5]=C: δ(3,C)=0 → state=0
• i=6, T[6]=A: δ(0,A)=1 → state=1
• i=7, T[7]=B: δ(1,B)=2 → state=2
• i=8, T[8]=A: δ(2,A)=3 → state=3 → Match at 6 (6 = 8-3+1)

The algorithm finds three occurrences at positions 0, 2, and 6, including the overlapping ones at 0 and 2. Each step is a single table lookup, demonstrating the O(n) scanning guarantee. If we had used a naive algorithm without overlap handling, the second occurrence at position 2 might have been missed after the first match consumed characters.

5. Complexity Analysis

The performance of finite automata string matching is divided into preprocessing (building δ) and matching (scanning T). The total time is the sum of both phases, and the space is dominated by the transition table. Understanding the trade-offs is essential for choosing this method over alternatives like KMP or Boyer-Moore.

In the naive construction, for each of the m+1 states and each of the |Σ| alphabet symbols, we test up to m+1 values of k, and each test requires an O(m) string comparison (checking suffix). This yields O(m³ × |Σ|) or more precisely O(m² × |Σ|) if suffix checks are optimized with incremental comparison, but still cubic in practice. The efficient construction using the prefix function reduces this to O(m × |Σ|) by reusing previously computed transitions, which is optimal for building a complete DFA.

The matching phase is where this algorithm shines. It performs exactly n state transitions, each O(1), for a total of O(n) time regardless of the pattern structure or text content. There is no best or worst case variation during scanning – it is always linear. This predictability is invaluable for real-time systems, unlike Boyer-Moore which can degrade, or naive search which depends heavily on the number of partial matches.

Detailed Complexity Table

Space complexity is the main drawback. The table requires (m+1) × |Σ| integers. For m=1000 and ASCII (|Σ|=256), this is about 256,000 integers (~1 MB), which is acceptable. For m=10,000 and Unicode (|Σ|≈ 1M), it becomes infeasible. This is why sparse representations or KMP's O(m) space failure function are preferred for large alphabets. However, for small alphabets like DNA (4), binary (2), or network protocols, the full table is extremely efficient and cache-friendly.

Best case vs worst case for matching is identical because the algorithm never backtracks or skips characters. Even if the text is all 'A's and the pattern is "AAAAAB", each character still causes one transition. This contrasts with Boyer-Moore, which can skip many characters in the best case (O(n/m)) but degrades to O(n×m) in the worst case without the Galil rule.

6. Variations and Optimizations

The classic finite automaton can be optimized in several directions depending on constraints: alphabet size, pattern length, number of patterns, and hardware target. The most important optimization is the connection to KMP.

The Knuth-Morris-Pratt algorithm can be viewed as a space-optimized finite automaton. Instead of storing the full δ table, KMP stores only the failure function π (size m) and computes transitions on the fly with a while loop. This reduces space from O(m × |Σ|) to O(m) at the cost of amortized O(1) but not strict O(1) per character (though still O(n) overall). For large alphabets, this is a crucial win. The efficient DFA construction shown earlier actually uses π to build δ, showing their deep relationship.

For multiple patterns, the natural extension is the Aho-Corasick automaton. It builds a trie of all patterns and adds failure links, creating a single DFA that can search for thousands of patterns simultaneously in O(n + total pattern length + number of matches) time. This is the backbone of intrusion detection systems like Snort and antivirus engines that must match against large signature databases in real time.

Bit-Parallel and Hardware Optimizations

When the pattern fits within a machine word (m ≤ 64), bit-parallel simulation of the NFA (nondeterministic automaton) using algorithms like Shift-Or / Shift-And can be faster than a DFA table. These use bitwise operations to update all states in parallel. For hardware (FPGA/ASIC), the DFA can be directly synthesized into logic gates, achieving one character per clock cycle at gigabits per second – impossible with algorithms that require variable-length loops.

Another optimization is alphabet compression. If the pattern only uses a subset of Σ, we can map characters to equivalence classes. For example, case-insensitive matching can map 'A' and 'a' to the same transition, halving the table width. For DNA, we only need 4 columns regardless of ASCII size.

Caching and prefetching also matter. Since scanning is a tight loop of table lookups, ensuring the transition table stays in L1/L2 cache dramatically improves performance. For very large m, splitting the pattern or using a two-level table (first level for high bytes) can help.

7. Real-World Applications

Finite automata string matching is not just a theoretical exercise; it powers critical infrastructure where predictable performance and streaming capability are non-negotiable.

In network security and intrusion detection, systems must inspect every packet payload against thousands of attack signatures at line speed (10-100 Gbps). A DFA can be implemented in hardware and processes each byte in constant time without buffering. Tools like Snort, Suricata, and firewalls use Aho-Corasick (multi-pattern DFA) to detect malicious strings like SQL injection payloads or virus signatures. The deterministic nature guarantees no packet is delayed due to algorithmic worst cases, which an attacker could otherwise exploit for denial-of-service.

Web servers and databases use finite automata for routing, tokenization, and query parsing. Lexical analyzers (lexers) in compilers and interpreters are essentially DFAs generated by tools like lex/flex. When a web server parses HTTP headers or a database parses SQL, it uses automata to recognize keywords and delimiters in a single pass. Text editors and grep implementations also rely on automata for regular expression matching, which generalizes string matching.

In bioinformatics, searching for DNA motifs, genes, or CRISPR target sequences in genomes (3 billion base pairs for human) requires linear-time scanning with tiny alphabets. A DFA for a DNA pattern with |Σ|=4 is extremely compact and fast. Similarly, log analysis and observability platforms (like Splunk or ELK) scan terabytes of logs for error patterns, and the O(n) guarantee ensures predictable query latency.

Application Summary Table

Even in high-level applications like JavaScript's String.prototype.search or Python's re engine, the underlying implementation for plain string search often falls back to automata-based methods when the pattern is compiled. The key takeaway is that whenever you need to scan a stream without the ability to look ahead or backtrack, a finite automaton is the correct abstraction.

8. Comparison with Alternatives

No single string matching algorithm is optimal for all scenarios. The choice depends on alphabet size, pattern length, text length, number of patterns, and whether preprocessing cost can be amortized. Finite automata excels at predictable scanning but pays a preprocessing and memory cost.

The naive algorithm is simple to implement and has O(1) extra space, but its O(n×m) worst case makes it unsuitable for adversarial inputs. Rabin-Karp uses hashing to achieve average O(n+m) and is excellent for searching for the same pattern in multiple texts or for plagiarism detection, but hash collisions require verification and its worst case remains O(n×m). Knuth-Morris-Pratt guarantees O(n+m) time and O(m) space and never backtracks in the text, making it ideal for streaming, but its per-character loop can be slightly slower than a DFA table lookup due to the while loop on mismatches.

Boyer-Moore and its variants (Horspool, Sunday) are often the fastest in practice for large alphabets and long patterns because they can skip characters. By aligning the pattern from the right and using bad-character and good-suffix heuristics, they achieve sublinear average time O(n/m). However, they are more complex to implement correctly and their worst case without modifications is O(n×m). For small alphabets like DNA, their skipping ability diminishes.

Feature Comparison Table

When to choose finite automata? Choose it when you need strict O(n) scanning with no variance, when the alphabet is small, when you can afford O(m×|Σ|) memory, when you need to process a stream character-by-character, or when you will search for the same pattern many times and can amortize the preprocessing cost. For a one-off search with a large alphabet and long pattern in a large text, Boyer-Moore may be faster. For minimal memory, KMP is better. For multiple patterns, extend to Aho-Corasick rather than running a single-pattern DFA multiple times.

9. Common Mistakes and Best Practices

Implementing finite automata string matching correctly requires attention to edge cases and performance pitfalls that are not obvious from the pseudocode.

A frequent mistake is incomplete alphabet handling. Many tutorials build δ only for characters appearing in the pattern. When scanning text, encountering a character outside this set causes a KeyError or incorrect transition. The DFA must be complete: every state must have a defined transition for every possible input character. In practice, this means either building a full table for the entire alphabet or explicitly handling the default case as δ(q, a) = 0 for unknown a, with a special check for a == pattern[0]. Failing to do this leads to missed matches or crashes on real-world data.

Another common error is mishandling overlapping matches and the accepting state. After reaching state m, some implementations reset to 0, which misses overlaps. The correct behavior is to continue as per δ(m, next_char), which already encodes the proper overlap via the prefix function. For example, searching for "AAA" in "AAAA" should yield matches at 0 and 1. Resetting to 0 after the first match would only find the match at 0. Always let the automaton transition naturally from the accepting state.

Off-by-one errors in state indexing are also prevalent. States are 0..m inclusive (m+1 states), but pattern indices are 0..m-1. Confusing pattern[q] when q==m leads to IndexError. The transition for q==m should be computed using the same rule, not by accessing pattern[m]. Similarly, reporting match positions as i - m instead of i - m + 1 shifts results by one.

Best Practices Checklist

• Validate inputs: Handle empty pattern (should match at every position) and empty text gracefully. Check that pattern length is not greater than text length if you want to early exit, though the automaton will naturally find zero matches.
• Choose representation wisely: For |Σ| > 100 and m > 100, use sparse dict representation or switch to KMP. For |Σ| ≤ 4, use a dense list-of-lists for speed. Profile memory usage before deploying.
• Precompute once, reuse many times: The DFA is pattern-specific, not text-specific. If you search for the same pattern in many texts (e.g., log files), build δ once and reuse it. This amortizes the O(m×|Σ|) cost.
• Escape and test with diverse alphabets: Test with patterns that have strong borders like "ABABAB", "AAAA", and "ABCABABC" to verify fallback logic. Test with text containing characters never seen in the pattern.
• Prefer efficient construction: Never use the naive O(m³) construction for m > 20. Always implement the prefix-function-based O(m×|Σ|) method. It is only slightly more code but orders of magnitude faster.
• Consider using Python's built-ins for final verification: While implementing for learning, compare your results against Python's find or regex for correctness on random tests.

Finally, remember that Python's string find (implemented in C using efficient algorithms like Two-Way or BMH) will almost always be faster than a pure Python DFA for single searches due to interpreter overhead. The value of implementing a DFA in Python is educational and for specialized cases like custom alphabets, hardware generation, or multi-pattern extensions where you control the automaton.

10. Interview Questions

Finite automata string matching is a favorite in algorithm interviews because it tests understanding of automata theory, preprocessing trade-offs, and the ability to optimize. Here are common questions and how to approach them.

Q1: Build the DFA transition table for pattern "ABABC" over alphabet {A,B,C} and explain the fallback for state 4 on input 'A'.

Answer approach: States 0..5. Compute δ(4, A). P4 = "ABAB", P4 + A = "ABABA". Longest prefix of "ABABC" that is suffix of "ABABA" is "ABA" (length 3). So δ(4,A)=3. Explain that "ABAB" has border "AB" (length 2), and adding "A" extends it to "ABA". Walk through the table construction methodically, showing you understand the suffix-prefix definition, not just memorizing. Mention that this fallback allows detecting overlapping patterns.

Q2: What is the time and space complexity of finite automata matching, and when would you prefer KMP over a full DFA?

Answer approach: State preprocessing O(m×|Σ|) efficient, matching O(n), space O(m×|Σ|). Prefer KMP when |Σ| is large (e.g., Unicode) because KMP uses O(m) space versus O(m×|Σ|). Also prefer KMP when memory is constrained or pattern is searched only once and preprocessing cost matters. DFA is preferred when alphabet is small, when you need strict O(1) per character for real-time/hardware, or when you will reuse the automaton many times. This shows you understand the memory-time trade-off.

Q3: How do you handle searching for multiple patterns efficiently? Can you extend the DFA idea?

Answer approach: Describe Aho-Corasick. Build a trie of all patterns, then add failure links (similar to prefix function but for a trie) and output links. The resulting automaton is still a DFA that processes text in O(n + total pattern length + number of matches). Explain that running a single-pattern DFA for each pattern would be O(k×n) for k patterns, while Aho-Corasick is O(n). Mention applications like virus scanning or keyword filtering. This demonstrates ability to generalize.

Q4: Given text "AAAAA" and pattern "AAA", how many matches does the DFA find and why is overlap handling important?

Answer approach: The DFA finds 3 matches at positions 0, 1, 2. Explain simulation: states progress 1→2→3 (match), then next 'A' from state 3 goes to 3 again? Actually for "AAA", δ(3,A)=3 because suffix "AAA" of "AAAA" is "AAA". So it stays in accepting state and reports each time. Overlap handling is crucial for patterns with self-overlap; naive reset to 0 would miss matches. Discuss that many real patterns (e.g., "abab" in "ababab") overlap and correctness requires proper automaton transitions.

Q5: Implement finite automata matcher without building the full table explicitly (space optimization).

Answer approach: Show the KMP-style on-the-fly transition: maintain state and while loop using prefix function. Pseudocode: while state > 0 and pattern[state] != c: state = pi[state-1]; if pattern[state]==c: state+=1. This is the sparse simulation. Explain that this reduces space to O(m) and still gives O(n) amortized time, though not strict O(1) per character. Code it cleanly and discuss that this is essentially simulating the DFA without materializing it. Interviewers look for this insight that DFA and KMP are two representations of the same idea.

Mastering these questions requires not just coding the algorithm but articulating the theory behind states, transitions, and trade-offs. Practice constructing small tables by hand and reasoning about borders and suffixes.