Lyndon array in Python
For each position, the length of the longest Lyndon word starting there.
- File
lyndon_array.py, 87 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/lyndon-array/. The authors are listed in prov/KRWVSH.jsonl.
from typing import Any, List, Sequence
def inverse_suffix_array(s: Sequence[Any]) -> List[int]:
"""Ranks of the suffixes of s, a proper prefix being smaller.
Prefix doubling with a sort: O(n log^2 n) time, O(n) space.
"""
n = len(s)
if n == 0:
return []
code = {c: k for k, c in enumerate(sorted(set(s)))}
rank = [code[c] for c in s]
k = 1
while True:
key = [(rank[i], rank[i + k] if i + k < n else -1) for i in range(n)]
order = sorted(range(n), key=key.__getitem__)
new = [0] * n
for r in range(1, n):
new[order[r]] = new[order[r - 1]] + (key[order[r]] != key[order[r - 1]])
rank = new
if rank[order[-1]] == n - 1:
return rank
k *= 2
class LyndonArray:
"""The Lyndon array of a sequence s over a totally ordered alphabet.
lam[i] is the length of the longest Lyndon word starting at index i
(0-based). Build: O(n log^2 n) time here (the stack pass is O(n));
query: O(1); factors: O(1) per factor. Space: O(n).
"""
def __init__(self, s: Sequence[Any]) -> None:
self.s = s
n = len(s)
# @line L1
rank = inverse_suffix_array(s)
# @line L2
lam = [0] * n
stack: List[int] = []
# @line L3
for i in range(n - 1, -1, -1):
# @line L4
while stack and rank[stack[-1]] > rank[i]:
# @line L5
stack.pop()
# @line L6
if not stack:
lam[i] = n - i
# @line L7
else:
lam[i] = stack[-1] - i
# @line L8
stack.append(i)
# @line L9
self.lam = lam
def query(self, i: int) -> int:
"""Length of the longest Lyndon word starting at i."""
# @line L10
return self.lam[i]
def factors(self, i: int = 0) -> List[int]:
"""Start indices of the Lyndon factorization of s[i:]."""
n = len(self.lam)
# @line L11
out: List[int] = []
# @line L12
while i < n:
# @line L13
out.append(i)
i += self.lam[i]
# @line L14
return out
def check_invariant(self) -> None:
"""Each lam[i] is in range, and the intervals [i, i + lam[i]) nest."""
n = len(self.lam)
for i in range(n):
assert 1 <= self.lam[i] <= n - i
for j in range(i + 1, i + self.lam[i]):
assert j + self.lam[j] <= i + self.lam[i]
test_lyndon_array.py 68 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lyndon-array/. The authors are listed in prov/KRWVSH.jsonl.
import itertools
import random
from typing import List
from lyndon_array import LyndonArray, inverse_suffix_array
def is_lyndon(w: str) -> bool:
return len(w) > 0 and all(w < w[i:] + w[:i] for i in range(1, len(w)))
def brute_lam(s: str) -> List[int]:
n = len(s)
return [max(m for m in range(1, n - i + 1) if is_lyndon(s[i : i + m])) for i in range(n)]
def brute_factors(s: str) -> List[int]:
# Greedy longest Lyndon prefix, which is the Lyndon factorization.
out, i = [], 0
while i < len(s):
out.append(i)
i += max(m for m in range(1, len(s) - i + 1) if is_lyndon(s[i : i + m]))
return out
def test_example() -> None:
s = "abaabaabb"
assert inverse_suffix_array(s) == [2, 6, 0, 3, 7, 1, 4, 8, 5]
a = LyndonArray(s)
a.check_invariant()
assert a.lam == [2, 1, 7, 2, 1, 4, 3, 1, 1]
assert a.query(2) == 7
assert a.factors(0) == [0, 2]
assert a.factors(3) == [3, 5]
def test_edges() -> None:
assert LyndonArray("").lam == []
assert LyndonArray("a").lam == [1]
assert LyndonArray("aa").lam == [1, 1]
assert LyndonArray("aba").lam == [2, 1, 1]
assert LyndonArray("ab").lam == [2, 1]
assert LyndonArray([2, 1, 3]).lam == [1, 2, 1]
def test_exhaustive_small() -> None:
for sigma in (1, 2, 3):
for n in range(0, 10 if sigma < 3 else 7):
for t in itertools.product("abc"[:sigma], repeat=n):
s = "".join(t)
a = LyndonArray(s)
assert a.lam == brute_lam(s), s
def test_random() -> None:
rng = random.Random(2003)
for _ in range(600):
sigma = rng.choice((1, 2, 3))
n = rng.randint(0, 30)
s = "".join(rng.choice("abc"[:sigma]) for _ in range(n))
a = LyndonArray(s)
a.check_invariant()
assert a.lam == brute_lam(s), s
i = rng.randint(0, n)
assert a.factors(i) == [i + f for f in brute_factors(s[i:])], (s, i)
What the next level needs
- the tests did not run in this build