Backward DAWG matching in Python
Scans windows right to left using a suffix automaton of the reversed pattern; sublinear on average.
- File
backward_dawg_matching.py, 76 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/backward-dawg-matching/. The authors are listed in prov/YJ949P.jsonl.
from collections.abc import Hashable, Sequence
def suffix_automaton(w: Sequence[Hashable]) -> tuple[list[dict], list[bool]]:
"""Suffix automaton of w: transitions (state 0 is initial) and terminal flags.
It accepts exactly the suffixes of w, and every factor of w labels a path from state 0.
"""
trans: list[dict] = [{}]
link = [-1]
length = [0]
last = 0
for c in w:
cur = len(trans)
trans.append({})
link.append(-1)
length.append(length[last] + 1)
p = last
while p != -1 and c not in trans[p]:
trans[p][c] = cur
p = link[p]
if p == -1:
link[cur] = 0
else:
q = trans[p][c]
if length[p] + 1 == length[q]:
link[cur] = q
else:
clone = len(trans)
trans.append(dict(trans[q]))
link.append(link[q])
length.append(length[p] + 1)
while p != -1 and trans[p].get(c) == q:
trans[p][c] = clone
p = link[p]
link[q] = link[cur] = clone
last = cur
terminal = [False] * len(trans)
p = last
while p != -1:
terminal[p] = True
p = link[p]
return trans, terminal
def backward_dawg_matching(text: Sequence[Hashable], pattern: Sequence[Hashable], stats: dict | None = None) -> list[int]:
"""All shifts s with text[s:s+m] == pattern, in increasing order.
If stats is a dict, stats["inspections"] receives the number of text characters read.
"""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
if stats is not None:
stats["inspections"] = 0
return list(range(n + 1))
trans, terminal = suffix_automaton(pattern[::-1]) # @line L3
out, inspections = [], 0
s = 0 # @line L4
while s <= n - m: # @line L5
q, j, shift = 0, m, m # @line L6
while j > 0 and q is not None: # @line L7
inspections += 1
q = trans[q].get(text[s + j - 1]) # @line L8
j -= 1
if q is not None and terminal[q]: # @line L9
if j > 0: # @line L10
shift = j
else:
out.append(s)
s += shift # @line L11
if stats is not None:
stats["inspections"] = inspections
return out
test_backward_dawg_matching.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/backward-dawg-matching/. The authors are listed in prov/YJ949P.jsonl.
import itertools
import random
from backward_dawg_matching import backward_dawg_matching, suffix_automaton
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 accepts(trans: list[dict], terminal: list[bool], w: str) -> tuple[bool, bool]:
q = 0
for c in w:
if c not in trans[q]:
return False, False
q = trans[q][c]
return True, terminal[q]
def test_automaton_against_definition() -> None:
for m in range(0, 7):
for p in itertools.product("ab", repeat=m):
w = "".join(p)
trans, terminal = suffix_automaton(w)
assert len(trans) <= max(m + 1, 2 * m - 1)
for k in range(0, m + 2):
for x in itertools.product("ab", repeat=k):
xs = "".join(x)
assert accepts(trans, terminal, xs) == (xs in w, w.endswith(xs))
def test_example() -> None:
stats: dict = {}
assert backward_dawg_matching("gcatcgcagagagtatacagtacg", "gcagagag", stats) == [5]
assert stats["inspections"] == 16
def test_edges() -> None:
assert backward_dawg_matching("abc", "") == [0, 1, 2, 3]
assert backward_dawg_matching("", "") == [0]
assert backward_dawg_matching("", "a") == []
assert backward_dawg_matching("ab", "abc") == []
assert backward_dawg_matching("a" * 10, "a" * 4) == list(range(7))
assert backward_dawg_matching("a" * 10, "baaa") == []
def test_skips_on_absent_characters() -> None:
stats: dict = {}
assert backward_dawg_matching("x" * 1000, "abcdefghij", stats) == []
assert stats["inspections"] == 100
def test_random_against_oracle() -> None:
rng = random.Random(1994)
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 backward_dawg_matching(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build