Computing the string-matching automaton transition function in Python

Builds the finite automaton for a pattern by computing, for each state and character, the longest pattern prefix that is a suffix of the input read.

File: string_matching_automaton_construction.py, 54 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

string_matching_automaton_construction.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/string-matching-automaton-construction/. The authors are listed in prov/HCTKVB.jsonl.

from collections.abc import Sequence


def compute_transition_function(pattern: Sequence[int], sigma: int) -> list[list[int]]:
    """delta[q][c] for states 0..m and characters 0..sigma-1 of an integer alphabet.

    delta[q][c] is the length of the longest prefix of pattern that is a suffix
    of pattern[:q] + [c].
    """
    m = len(pattern)  # @line L1
    delta = [[0] * sigma for _ in range(m + 1)]
    if m > 0:  # @line L2
        delta[0][pattern[0]] = 1
    x = 0  # @line L3
    for q in range(1, m + 1):  # @line L4
        row, lag = delta[q], delta[x]
        for c in range(sigma):  # @line L5
            row[c] = lag[c]  # @line L6
        if q < m:  # @line L7
            row[pattern[q]] = q + 1  # @line L8
            x = delta[x][pattern[q]]  # @line L9
    return delta  # @line L10


def compute_transition_function_naive(pattern: Sequence[int], sigma: int) -> list[list[int]]:
    """The direct method: try every k from min(m, q + 1) down; O(m^3 sigma) time."""
    m = len(pattern)
    p = list(pattern)
    delta = [[0] * sigma for _ in range(m + 1)]
    for q in range(m + 1):
        for c in range(sigma):
            w = p[:q] + [c]
            k = min(m, q + 1)
            while k > 0 and p[:k] != w[len(w) - k :]:
                k -= 1
            delta[q][c] = k
    return delta


def automaton_search(text: Sequence[int], pattern: Sequence[int], sigma: int) -> list[int]:
    """All shifts of pattern in text, both over the alphabet 0..sigma-1."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    delta = compute_transition_function(pattern, sigma)
    q, out = 0, []
    for i, c in enumerate(text):
        q = delta[q][c]
        if q == m:
            out.append(i - m + 1)
    return out

test_string_matching_automaton_construction.py 60 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/string-matching-automaton-construction/. The authors are listed in prov/HCTKVB.jsonl.

import random

from string_matching_automaton_construction import (
    automaton_search,
    compute_transition_function,
    compute_transition_function_naive,
)


def oracle(t: list[int], p: list[int]) -> list[int]:
    return [s for s in range(len(t) - len(p) + 1) if t[s : s + len(p)] == p]


def enc(s: str) -> list[int]:
    return [ord(ch) - ord("a") for ch in s]


def test_example() -> None:
    delta = compute_transition_function(enc("ababaca"), 3)
    assert delta == [
        [1, 0, 0],
        [1, 2, 0],
        [3, 0, 0],
        [1, 4, 0],
        [5, 0, 0],
        [1, 4, 6],
        [7, 0, 0],
        [1, 2, 0],
    ]
    assert automaton_search(enc("abababacaba"), enc("ababaca"), 3) == [2]


def test_edges() -> None:
    assert compute_transition_function([], 2) == [[0, 0]]
    assert automaton_search(enc("abc"), [], 3) == [0, 1, 2, 3]
    assert automaton_search([], [], 1) == [0]
    assert automaton_search([], [0], 1) == []
    assert automaton_search(enc("ab"), enc("abc"), 3) == []
    assert automaton_search([0] * 10, [0] * 4, 1) == list(range(7))
    assert automaton_search([0] * 10, enc("aaab"), 2) == []


def test_table_against_naive() -> None:
    rng = random.Random(5)
    for sigma in (1, 2, 4):
        for _ in range(300):
            p = [rng.randrange(sigma) for _ in range(rng.randint(0, 9))]
            assert compute_transition_function(p, sigma) == compute_transition_function_naive(p, sigma)


def test_random_against_oracle() -> None:
    rng = random.Random(1990)
    for sigma in (1, 2, 4):
        for _ in range(700):
            t = [rng.randrange(sigma) for _ in range(rng.randint(0, 40))]
            p = [rng.randrange(sigma) for _ in range(rng.randint(0, 7))]
            assert automaton_search(t, p, sigma) == oracle(t, p)

What the next level needs

the tests did not run in this build

Read the full page about Computing the string-matching automaton transition function