String-matching automaton in Python
A DFA over the alphabet whose state is the longest pattern prefix matching the current text suffix; one transition per text character.
- File
string_matching_automaton.py, 52 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/string-matching-automaton/. The authors are listed in prov/3VKE1X.jsonl.
from collections.abc import Hashable, Iterable, Sequence
class StringMatchingAutomaton:
"""The DFA of a pattern: state q means that the last q characters read equal pattern[:q].
Columns are indexed by the distinct characters of the pattern; every other
character shares one extra column, since it leads to state 0 from any state.
"""
def __init__(self, pattern: Sequence[Hashable]) -> None:
m = len(pattern)
self.m = m
self.column = {}
for ch in pattern:
self.column.setdefault(ch, len(self.column))
sigma = len(self.column) + 1 # the last column is "any other character"
p = [self.column[ch] for ch in pattern]
delta = [[0] * sigma for _ in range(m + 1)]
if m > 0:
delta[0][p[0]] = 1
x = 0 # state reached on pattern[1:q]
for q in range(1, m + 1):
delta[q] = list(delta[x])
if q < m:
delta[q][p[q]] = q + 1
x = delta[x][p[q]]
self.delta = delta
self.other = sigma - 1
def step(self, q: int, ch: Hashable) -> int:
"""The transition delta(q, ch), in O(1) expected time."""
return self.delta[q][self.column.get(ch, self.other)]
def search(self, text: Iterable[Hashable]) -> list[int]:
"""All shifts of the pattern in text, reading each character once."""
m = self.m # @line L1
if m == 0: # @line L2
return list(range(sum(1 for _ in text) + 1))
q, out = 0, [] # @line L3
for i, ch in enumerate(text): # @line L4
q = self.step(q, ch) # @line L5
if q == m: # @line L6
out.append(i - m + 1) # @line L7
return out
def automaton_search(text: Sequence[Hashable], pattern: Sequence[Hashable]) -> list[int]:
return StringMatchingAutomaton(pattern).search(text)
test_string_matching_automaton.py 53 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/string-matching-automaton/. The authors are listed in prov/3VKE1X.jsonl.
import random
from string_matching_automaton import StringMatchingAutomaton, automaton_search
def oracle(t: str, p: str) -> list[int]:
return [s for s in range(len(t) - len(p) + 1) if t.startswith(p, s)]
def sigma_oracle(p: str, w: str) -> int:
return max(k for k in range(min(len(p), len(w)) + 1) if w.endswith(p[:k]))
def test_example() -> None:
a = StringMatchingAutomaton("ababaca")
table = [[a.step(q, ch) for ch in "abc"] for q in range(8)]
assert table == [[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 a.search("abababacaba") == [2]
assert a.step(5, "z") == 0
def test_edges() -> None:
assert automaton_search("abc", "") == [0, 1, 2, 3]
assert automaton_search("", "") == [0]
assert automaton_search("", "a") == []
assert automaton_search("ab", "abc") == []
assert automaton_search("a" * 10, "a" * 4) == list(range(7))
assert automaton_search("a" * 10, "aaab") == []
def test_states_are_sigma() -> None:
rng = random.Random(11)
for alphabet in ("a", "ab", "abcd"):
for _ in range(200):
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(1, 8)))
t = "".join(rng.choice(alphabet + "z") for _ in range(rng.randint(0, 25)))
a = StringMatchingAutomaton(p)
q = 0
for i, ch in enumerate(t):
q = a.step(q, ch)
assert q == sigma_oracle(p, t[: i + 1])
def test_random_against_oracle() -> None:
rng = random.Random(1968)
for alphabet in ("a", "ab", "abcd"):
for _ in range(700):
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 40)))
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 7)))
assert automaton_search(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build