Two-way algorithm in Python
Linear-time, constant-space matching using a critical factorization of the pattern.
- File
two_way_string_matching.py, 100 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/two-way-string-matching/. The authors are listed in prov/5X5RDM.jsonl.
from collections.abc import Sequence
from typing import Any
def maximal_suffix(p: Sequence[Any], reverse: bool) -> tuple[int, int]:
"""Return (ms, per): the maximal suffix of p for the order < (or > if reverse)
is p[ms+1:], and per is its smallest period. Uses O(1) extra space."""
m = len(p)
ms, j, k, per = -1, 0, 1, 1 # @line L20
while j + k < m: # @line L21
a, b = p[j + k], p[ms + k] # @line L22
if (a > b) if reverse else (a < b): # @line L23
j += k
k = 1
per = j - ms
elif a == b: # @line L24
if k != per:
k += 1
else:
j += per
k = 1
else: # @line L25
ms = j
j = ms + 1
k = per = 1
return ms, per # @line L26
def critical_factorization(p: Sequence[Any]) -> tuple[int, int]:
"""Return (ell, per) where (p[:ell+1], p[ell+1:]) is a critical factorization
and per is the period of the longer of the two maximal suffixes."""
i, per1 = maximal_suffix(p, False) # @line L27
j, per2 = maximal_suffix(p, True)
return (i, per1) if i > j else (j, per2) # @line L28
def two_way_string_matching(text: Sequence[Any], pattern: Sequence[Any], stats: dict | None = None) -> list[int]:
"""All shifts s with text[s:s+m] == pattern, in increasing order.
Characters must be totally ordered. If stats is a dict, stats["comparisons"]
receives the number of text character comparisons.
"""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
if stats is not None:
stats["comparisons"] = 0
return list(range(n + 1))
ell, per = critical_factorization(pattern) # @line L3
out, c = [], 0
if pattern[: ell + 1] == pattern[per : per + ell + 1]: # @line L4
s, memory = 0, -1 # @line L5
while s <= n - m: # @line L6
i = max(ell, memory) + 1 # @line L7
while i < m: # @line L8
c += 1
if pattern[i] != text[s + i]:
break
i += 1
if i >= m: # @line L9
i = ell # @line L10
while i > memory:
c += 1
if pattern[i] != text[s + i]:
break
i -= 1
if i <= memory: # @line L11
out.append(s)
s += per # @line L12
memory = m - per - 1
else:
s += i - ell # @line L13
memory = -1
else: # @line L14
q = max(ell + 1, m - ell - 1) + 1 # @line L15
s = 0
while s <= n - m: # @line L16
i = ell + 1 # @line L17
while i < m:
c += 1
if pattern[i] != text[s + i]:
break
i += 1
if i >= m: # @line L18
i = ell
while i >= 0:
c += 1
if pattern[i] != text[s + i]:
break
i -= 1
if i < 0:
out.append(s)
s += q
else:
s += i - ell # @line L19
if stats is not None:
stats["comparisons"] = c
return out
test_two_way_string_matching.py 76 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/two-way-string-matching/. The authors are listed in prov/5X5RDM.jsonl.
import itertools
import random
from two_way_string_matching import critical_factorization, two_way_string_matching
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 period(w: str) -> int:
return next(d for d in range(1, len(w) + 1) if all(w[i] == w[i + d] for i in range(len(w) - d)))
def local_period(w: str, cut: int) -> int:
for r in range(1, len(w) + 1):
if all(w[i] == w[i + r] for i in range(max(0, cut - r), cut) if i + r < len(w)):
return r
return len(w)
def test_critical_factorization() -> None:
for m in range(1, 8):
for p in itertools.product("abc", repeat=m):
w = "".join(p)
ell, per = critical_factorization(w)
assert local_period(w, ell + 1) == period(w)
assert ell + 1 < period(w)
if w[: ell + 1] == w[per : per + ell + 1]:
assert per == period(w)
else:
assert period(w) > max(ell + 1, m - ell - 1)
def test_example() -> None:
assert critical_factorization("gcagagag") == (1, 2)
stats: dict = {}
assert two_way_string_matching("gcatcgcagagagtatacagtacg", "gcagagag", stats) == [5]
assert stats["comparisons"] == 20
stats = {}
assert two_way_string_matching("abaabaabaabaab", "aabaab", stats) == [2, 5, 8]
assert stats["comparisons"] == 14
def test_edges() -> None:
assert two_way_string_matching("abc", "") == [0, 1, 2, 3]
assert two_way_string_matching("", "") == [0]
assert two_way_string_matching("", "a") == []
assert two_way_string_matching("ab", "abc") == []
assert two_way_string_matching("a" * 10, "a" * 4) == list(range(7))
assert two_way_string_matching("a" * 10, "baaa") == []
assert two_way_string_matching([3, 1, 3, 1, 3], [3, 1, 3]) == [0, 2]
def test_comparison_bound() -> None:
for m in range(1, 6):
for p in itertools.product("ab", repeat=m):
ps = "".join(p)
for n in range(m, 11):
for t in itertools.product("ab", repeat=n):
ts = "".join(t)
stats: dict = {}
assert two_way_string_matching(ts, ps, stats) == oracle(ts, ps)
assert stats["comparisons"] <= 2 * n - m
def test_random_against_oracle() -> None:
rng = random.Random(1991)
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 two_way_string_matching(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build