Suffix Array

Calculates the suffix array (i.e., the lexicographical order of all suffixes) and the lcp array (i.e., the length of the longest common prefix of consecutive suffixes) of a string.

As of 2025/12/31, this implementation is the fastest in Python3 (PyPy).

__init__

Arguments

• S: str: input string

Complexities

• time: $O(n)$
• space: $O(n)$

sa

Returns

• list[int]: suffix array

lcp

Returns

• list[int]: lcp array

Code Test

Run

Standard Output

Standard Error