58 lines
1.5 KiB
Python
58 lines
1.5 KiB
Python
"""Longest common prefix (LCP) array for a suffix array.
|
|
|
|
Given a text (str or bytes) and its suffix array (list of starting positions
|
|
in ascending suffix order), compute the LCP array where lcp[i] is the length
|
|
of the longest common prefix of suffix SA[i-1] and suffix SA[i], with
|
|
lcp[0] = 0 by convention.
|
|
|
|
Uses Kasai's O(n) algorithm: walk suffixes in text order, maintaining the
|
|
current match length and decrementing by one each step.
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
|
|
def build_suffix_array(text):
|
|
"""Naive O(n^2 log n) suffix array; fine for modest n."""
|
|
n = len(text)
|
|
return sorted(range(n), key=lambda i: text[i:])
|
|
|
|
|
|
def build_lcp(text, sa):
|
|
n = len(text)
|
|
if len(sa) != n:
|
|
raise ValueError("suffix array length must equal text length")
|
|
if sorted(sa) != list(range(n)):
|
|
raise ValueError("invalid suffix array")
|
|
rank = [0] * n
|
|
for i, s in enumerate(sa):
|
|
rank[s] = i
|
|
lcp = [0] * n
|
|
k = 0
|
|
for i in range(n):
|
|
if rank[i] == 0:
|
|
k = 0
|
|
continue
|
|
j = sa[rank[i] - 1]
|
|
while i + k < n and j + k < n and text[i + k] == text[j + k]:
|
|
k += 1
|
|
lcp[rank[i]] = k
|
|
if k > 0:
|
|
k -= 1
|
|
return lcp
|
|
|
|
|
|
def lcp_of(text, i, j):
|
|
"""Direct LCP of suffixes starting at i and j."""
|
|
n = len(text)
|
|
k = 0
|
|
while i + k < n and j + k < n and text[i + k] == text[j + k]:
|
|
k += 1
|
|
return k
|
|
|
|
|
|
if __name__ == "__main__":
|
|
t = "banana"
|
|
sa = build_suffix_array(t)
|
|
print(sa)
|
|
print(build_lcp(t, sa))
|