Offensive Security Researcher & Quantum Cryptography Analyst

String Matching with Finite Automata: Complete Guide with Examples

Abdul Wahab Junaid
String Matching with Finite Automata

I use the finite automaton approach to string matching whenever I want to search for a pattern in a text using a precomputed state machine that examines each text character exactly once. I think of this method as building a specialized machine, tailored to a specific pattern, that transitions between states representing “how much of the pattern have I matched so far,” and reaches an accepting state precisely when the pattern has been found. I find this approach conceptually elegant because it separates the matching logic (a generic automaton simulation) from the pattern-specific knowledge (encoded entirely in the precomputed transition table).

History and Background

I trace the theoretical foundation of automaton-based string matching to the broader development of automata theory in the 1950s, particularly the work of Stephen Kleene on regular expressions and finite automata, and Michael Rabin and Dana Scott’s 1959 paper formalizing nondeterministic automata. I see the specific application to string matching popularized through its treatment in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms, which presents it as a natural bridge between formal automata theory and practical string search algorithms, and closely related in spirit to the automaton implicit within the KMP algorithm’s failure function. I regard this method as historically important because it demonstrates the deep connection between string matching and formal language theory — the pattern-matching automaton is, in essence, a deterministic finite automaton recognizing the language of all strings ending in the pattern $P$.

Problem Statement

I use the finite automaton method to solve the same fundamental problem as other string-matching algorithms: given a text $T$ of length $n$ and a pattern $P$ of length $m$, I want to find all positions where $P$ occurs in $T$. I want an algorithm where, once I’ve built the automaton, each character of the text is processed in strictly constant time per character, giving me a clean linear-time guarantee on the scanning phase, independent of how the automaton itself was constructed.

Core Concepts

I build a deterministic finite automaton (DFA) with $m+1$ states, labeled $0$ through $m$, where state $q$ represents “the longest prefix of $P$ that is a suffix of the text read so far has length $q$.” I define a transition function $\delta(q, c)$ that, given the current state $q$ and the next character $c$ read from the text, returns the next state. State $m$ (having matched the entire pattern) is the unique accepting state. I rely on the concept of the alphabet $\Sigma$, since the transition function must be defined for every state and every possible character in $\Sigma$.

How It Works

I follow this process when applying the automaton-based method:

  1. Construction phase: I build the transition table $\delta(q, c)$ for every state $q \in {0, \ldots, m}$ and every character $c \in \Sigma$, based on the pattern $P$.
  2. Matching phase: I initialize the current state $q = 0$, then scan the text left to right, updating $q = \delta(q, T[i])$ for each character.
  3. Whenever $q$ reaches $m$ (the accepting state), I record a match ending at the current text position.
  4. I continue scanning until the end of the text, since the automaton naturally continues seeking further matches without any special reset logic.

Working Principle

I understand the internal logic of this method as precomputing, once and for all, the answer to the question “if I’m currently in a state representing $q$ matched characters, and I see character $c$ next, what is the new longest matched prefix?” This requires checking, for every possible next character, what the longest prefix of $P$ that is also a suffix of $(P[0..q-1] + c)$ would be. Because this computation is done entirely during construction, the matching phase itself becomes trivial: I simply follow precomputed transitions, examining each text character exactly once with $O(1)$ work per character, regardless of how complex the pattern’s internal structure is.

Mathematical Foundation

I define the transition function formally:

$$ \delta(q, c) = \text{length of the longest prefix of } P \text{ that is a suffix of } P[0..q-1] + c $$

I compute this using the following characterization, which I use directly in the construction algorithm: I check, for $k$ from $\min(m, q+1)$ down to $0$, whether $P[0..k-1]$ is a suffix of $P[0..q-1] + c$, and I take the largest such $k$.

I state the time complexity of the naive construction algorithm, which checks this condition directly for every state and character:

$$ O(m^3 |\Sigma|) $$

since for each of the $m+1$ states and $|\Sigma|$ characters, I may need up to $O(m)$ candidate lengths $k$, each requiring an $O(m)$ suffix comparison.

I note that a more refined construction algorithm, which reuses previously computed transitions (similar in spirit to the KMP failure function), reduces this to:

$$ O(m|\Sigma|) $$

by computing $\delta(q, c)$ in terms of $\delta(\pi[q-1], c)$ when $c \neq P[q]$, where $\pi$ is the KMP-style failure function — avoiding redundant recomputation from scratch for every state.

I formally justify the matching phase’s $O(n)$ scanning time since exactly one transition, an $O(1)$ table lookup, is performed per text character:

$$ T_{\text{match}}(n) = O(n) $$

Diagrams

flowchart TD
    A[Input: pattern P, alphabet Sigma] --> B[Build transition table delta for states 0..m]
    B --> C[Initialize state q = 0]
    C --> D[Read next character c from text T]
    D --> E[Set q = delta of q and c]
    E --> F{q equals m?}
    F -->|Yes| G[Record match, continue scanning]
    F -->|No| H{More text remaining?}
    G --> H
    H -->|Yes| D
    H -->|No| I[Return all matches]

Pseudocode

I write pseudocode for both constructing the automaton (naive version, for clarity) and using it to scan the text:

function COMPUTE_TRANSITION_TABLE(P, Sigma):
    m = length(P)
    delta = table of size (m+1) x |Sigma|

    for q from 0 to m:
        for each character c in Sigma:
            k = min(m, q + 1)
            while k > 0 and NOT IS_SUFFIX(P[0..k-1], P[0..q-1] + c):
                k = k - 1
            delta[q][c] = k

    return delta

function FA_STRING_MATCHER(T, P, delta):
    n = length(T)
    m = length(P)
    q = 0
    matches = empty list

    for i from 0 to n - 1:
        q = delta[q][T[i]]
        if q == m:
            matches.append(i - m + 1)

    return matches

Step-by-Step Example

I build the automaton for pattern $P = \text{“aba”}$ over alphabet ${a, b}$, then match against text $T = \text{“ababa”}$.

Transition table for “aba”:

State $q$on ‘a’on ‘b’
010
112
230
3 (accept)12

Scanning $T = \text{“ababa”}$:

  1. Start at $q=0$. Read ‘a’: $q = \delta(0, a) = 1$.
  2. Read ‘b’: $q = \delta(1, b) = 2$.
  3. Read ‘a’: $q = \delta(2, a) = 3$. State 3 is accepting — I record a match ending at index 2 (starting at index 0).
  4. Read ‘b’: $q = \delta(3, b) = 2$.
  5. Read ‘a’: $q = \delta(2, a) = 3$. Accepting again — I record a match ending at index 4 (starting at index 2).

I find matches starting at text indices 0 and 2, correctly identifying both overlapping occurrences of “aba” in “ababa”.

Time Complexity

I establish that the matching phase runs in $O(n)$ time, since I perform exactly one table lookup per text character. I establish that the naive construction phase runs in $O(m^3|\Sigma|)$ time, though the optimized construction (reusing KMP-style failure information) reduces this to $O(m|\Sigma|)$. I note the combined complexity is $O(m|\Sigma| + n)$ using the optimized construction, which I consider excellent when the same automaton is reused across many different texts, since the (often larger) construction cost is paid only once. This bound holds uniformly across best, average, and worst cases for the matching phase, since exactly $n$ transitions are always performed regardless of the text’s content.

Space Complexity

I require $O(m|\Sigma|)$ space to store the full transition table, since I need an entry for every combination of state (there are $m+1$ of them) and character in the alphabet. I consider this the primary drawback relative to KMP, which requires only $O(m)$ space for its failure function table — the automaton trades additional space for simpler, branch-free matching logic.

Correctness Analysis

I justify the correctness of the automaton by the invariant maintained at every state $q$: after processing text position $i$, $q$ always equals the length of the longest prefix of $P$ that is also a suffix of $T[0..i]$. I prove this invariant is preserved by the transition function’s definition itself — $\delta(q,c)$ is defined precisely as the new longest matching prefix-suffix length after appending character $c$ to a text whose current longest matching prefix-suffix has length $q$. Since this invariant holds after every character, whenever $q$ reaches $m$, I have proven that the full pattern $P$ is exactly a suffix of the text read so far — meaning a match has genuinely occurred ending at the current position, with no false positives or missed matches possible given the invariant.

Advantages

Disadvantages

Applications

I apply automaton-based string matching in:

Implementation in C

I implement the automaton-based string matcher in C, using the naive construction algorithm for clarity, with comments:

#include <stdio.h>
#include <string.h>

#define ALPHABET_SIZE 256

// I check whether string 'a' (of given length) is a suffix of string 'b' (of given length)
int isSuffix(const char* a, int aLen, const char* b, int bLen) {
    if (aLen > bLen) return 0;
    return strncmp(a, b + (bLen - aLen), aLen) == 0;
}

// I build the transition table for pattern P using the naive O(m^3 * |Sigma|) method
void buildAutomaton(const char* P, int m, int delta[][ALPHABET_SIZE]) {
    for (int q = 0; q <= m; q++) {
        for (int c = 0; c < ALPHABET_SIZE; c++) {
            int k = (m < q + 1) ? m : q + 1;

            char extended[m + 2];
            memcpy(extended, P, q);
            extended[q] = (char)c;
            int extendedLen = q + 1;

            while (k > 0 && !isSuffix(P, k, extended, extendedLen)) {
                k--;
            }
            delta[q][c] = k;
        }
    }
}

// I scan text T using the precomputed automaton
void faStringMatcher(const char* T, int n, int m, int delta[][ALPHABET_SIZE]) {
    int q = 0;
    for (int i = 0; i < n; i++) {
        q = delta[q][(unsigned char)T[i]];
        if (q == m) {
            printf("Match found at index %d\n", i - m + 1);
        }
    }
}

int main() {
    const char* P = "aba";
    const char* T = "ababa";
    int m = strlen(P);
    int n = strlen(T);

    static int delta[4][ALPHABET_SIZE]; // m+1 states for pattern "aba"

    buildAutomaton(P, m, delta);
    faStringMatcher(T, n, m, delta);

    return 0;
}

Sample Input and Output

I use P = "aba" and T = "ababa" as input, and I expect:

Match found at index 0
Match found at index 2

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version