Z-algorithm in Python
Computes the longest common prefix of each suffix with the string; linear-time matching.
- File
z_algorithm.py, 41 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/z-algorithm/. The authors are listed in prov/7JPXK4.jsonl.
from collections.abc import Sequence
def z_array(s: Sequence) -> list[int]:
"""Z[k] = length of the longest common prefix of s and s[k:]; Z[0] = len(s)."""
big_n = len(s) # @line L1
if big_n == 0:
return []
z = [0] * big_n
z[0] = big_n
left = right = 0 # s[left:right] == s[0:right-left], right maximal so far
for k in range(1, big_n): # @line L2
if k < right: # @line L3
zk = min(right - k, z[k - left])
else:
zk = 0
while k + zk < big_n and s[zk] == s[k + zk]: # @line L4
zk += 1 # @line L5
z[k] = zk
if k + zk > right: # @line L6
left, right = k, k + zk
return z # @line L7
_SEPARATOR = object() # equal only to itself, so it is in no alphabet
def z_search(text: Sequence, pattern: Sequence) -> list[int]:
"""All shifts s with text[s:s+len(pattern)] == pattern, in increasing order."""
m, n = len(pattern), len(text) # @line L8
if m == 0: # @line L9
return list(range(n + 1))
z = z_array(list(pattern) + [_SEPARATOR] + list(text)) # @line L10
out = []
for s in range(n - m + 1): # @line L11
if z[m + 1 + s] == m: # @line L12
out.append(s)
return out
test_z_algorithm.py 60 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/z-algorithm/. The authors are listed in prov/7JPXK4.jsonl.
import random
from z_algorithm import z_array, z_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 z_oracle(s: str) -> list[int]:
out = []
for k in range(len(s)):
j = 0
while k + j < len(s) and s[j] == s[k + j]:
j += 1
out.append(j)
return out
def test_example() -> None:
assert z_array("aabxaabxay") == [10, 1, 0, 0, 5, 1, 0, 0, 1, 0]
assert z_array("aab$baabaaab") == [12, 1, 0, 0, 0, 3, 1, 0, 2, 3, 1, 0]
assert z_search("baabaaab", "aab") == [1, 5]
def test_edges() -> None:
assert z_array("") == []
assert z_array("a") == [1]
assert z_array("aaaa") == [4, 3, 2, 1]
assert z_search("abc", "") == [0, 1, 2, 3]
assert z_search("", "") == [0]
assert z_search("", "a") == []
assert z_search("ab", "abc") == []
assert z_search("a" * 10, "a" * 4) == list(range(7))
assert z_search("a" * 10, "aaab") == []
def test_separator_not_matched() -> None:
# Without a separator the value at a text position could exceed m.
assert z_search("aaaa", "aa") == [0, 1, 2]
def test_z_array_against_definition() -> None:
rng = random.Random(7)
for alphabet in ("a", "ab", "abcd"):
for _ in range(400):
s = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 30)))
assert z_array(s) == z_oracle(s)
def test_random_against_oracle() -> None:
rng = random.Random(1997)
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 z_search(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build