Suffix Arrays, LCP & Range Queries

Sorting Suffixes and Sentinel Conventions

For a string $S$ of length $N$, the suffix array $\operatorname{SA}$ is a permutation of $\{0,1,\dots,N-1\}$ such that

$$ S[\operatorname{SA}[k]\dots N-1] \lt_{\mathrm{lex}} S[\operatorname{SA}[k+1]\dots N-1] $$

for every $0\leq k\lt N-1$. Its inverse, the rank array, satisfies $\operatorname{Rank}[\operatorname{SA}[k]]=k$. The suffix array stores starting positions rather than suffix copies, so its final representation occupies $O(N)$ integers.

Many construction algorithms append a unique sentinel $\$$. It must occur nowhere in the input and compare strictly below every real symbol. The suffix consisting only of $\$$ is then first, every cyclic shift of $S\$$ is distinct, and sorting cyclic shifts is equivalent to sorting its suffixes. If the input alphabet is arbitrary, coordinate compression sorts the distinct symbols and maps them order-preservingly to $1,2,\dots,\sigma$ while reserving $0$ for the sentinel. Merely choosing the character '$' is unsafe unless its uniqueness and ordering are guaranteed by the application.

Prefix-Doubling Construction

Naively sorting suffixes with full lexicographic comparisons can require $O(N^2\log N)$ time. Prefix doubling instead assigns equivalence classes to prefixes whose inspected length doubles each round.

After round $k$, $C_k[i]$ identifies the length-$2^k$ prefix beginning at $i$. A length-$2^{k+1}$ prefix is represented by

$$ \bigl(C_k[i],C_k[(i+2^k)\bmod N]\bigr). $$

With a unique sentinel, these pairs may be sorted by shifting each suffix position backward by $2^k$ and performing one stable counting sort on the first class. Classes lie in $[0,N-1]$, so each round costs $O(N)$. At most $\lceil\log_2N\rceil$ rounds are needed, giving $O(N\log N)$ time and $O(N)$ auxiliary space. Using a general comparison sort on the pairs instead would cost $O(N\log^2N)$ overall.

def build_suffix_array(text: str) -> list[int]:
    """Return suffix starts for text in O(n log n) time."""
    if "\0" in text:
        raise ValueError("input contains the reserved sentinel")

    # Coordinate compression reserves class 0 for the unique sentinel.
    alphabet = {ch: i + 1 for i, ch in enumerate(sorted(set(text)))}
    values = [alphabet[ch] for ch in text] + [0]
    n = len(values)

    sa = sorted(range(n), key=values.__getitem__)
    classes = [0] * n
    for i in range(1, n):
        classes[sa[i]] = classes[sa[i - 1]] + (
            values[sa[i]] != values[sa[i - 1]]
        )

    length = 1
    while length < n:
        shifted = [(position - length) % n for position in sa]

        class_count = classes[sa[-1]] + 1
        count = [0] * class_count
        for position in shifted:
            count[classes[position]] += 1

        starts = [0] * class_count
        for c in range(1, class_count):
            starts[c] = starts[c - 1] + count[c - 1]

        new_sa = [0] * n
        for position in shifted:
            c = classes[position]
            new_sa[starts[c]] = position
            starts[c] += 1
        sa = new_sa

        new_classes = [0] * n
        for i in range(1, n):
            previous = (classes[sa[i - 1]], classes[(sa[i - 1] + length) % n])
            current = (classes[sa[i]], classes[(sa[i] + length) % n])
            new_classes[sa[i]] = new_classes[sa[i - 1]] + (current != previous)
        classes = new_classes

        if classes[sa[-1]] == n - 1:
            break
        length *= 2

    return sa  # Includes the sentinel suffix at position len(text).


if __name__ == "__main__":
    text = "banana"
    sa = build_suffix_array(text)
    assert sa == [6, 5, 3, 1, 0, 4, 2]
    print(sa)
    for start in sa:
        suffix = (text + "$")[start:]
        print(start, suffix)

Linear-Time Construction Overview

Linear-time construction removes the doubling factor by sorting a carefully chosen subset of suffixes and inducing the rest. These algorithms require an integer alphabet whose symbols can be bucketed in linear time.

DC3, also called the skew algorithm, recursively sorts suffixes at positions not congruent to $0$ modulo $3$ using triples, then merges them with the remaining suffixes. SA-IS classifies suffixes as S-type or L-type, directly sorts the leftmost S-type (LMS) suffixes, and induces the order of all remaining suffixes through bucket boundaries.

Their $O(N)$ bounds are theoretically stronger, but prefix doubling is often shorter and easier to verify. SA-IS is attractive in mature libraries because it combines linear time with good practical memory behavior.

Kasai LCP and RMQ

Using the convention $\operatorname{LCP}[0]=0$, define

$$ \operatorname{LCP}[k] = \operatorname{lcp}\bigl( S[\operatorname{SA}[k-1]\dots], S[\operatorname{SA}[k]\dots] \bigr) \quad\text{for }1\leq k\lt N. $$

Kasai's algorithm computes this array in $O(N)$ time. If the suffix beginning at $i$ shares $h$ leading symbols with its lexicographic predecessor, then after removing the first symbol, the suffix beginning at $i+1$ shares at least $h-1$ symbols with its own predecessor. Kasai retains this lower bound, extends comparisons as needed, and decreases $h$ by at most one per text position. Consequently, the total number of successful extensions is linear.

For suffixes beginning at $i$ and $j$, let $r_i=\operatorname{Rank}[i]$ and $r_j=\operatorname{Rank}[j]$, with $r_i\lt r_j$. Their common-prefix length is

$$ \operatorname{lcp}(S[i\dots],S[j\dots]) = \min_{r_i\lt k\leq r_j}\operatorname{LCP}[k]. $$

Thus arbitrary suffix-LCP queries reduce to range-minimum queries. A sparse table uses $O(N\log N)$ preprocessing and space with $O(1)$ queries; a segment tree uses $O(N)$ space and $O(\log N)$ queries; an Euler-tour RMQ reduction can achieve linear preprocessing and constant-time queries.

Substring Analytics with SA and LCP

Suffixes beginning with a pattern $P$ occupy one contiguous suffix-array interval. Two binary searches find its lower and upper boundaries. Straightforward comparison costs $O(\lvert P\rvert\log N)$; LCP-aware searching avoids rechecking known prefixes and can reach $O(\lvert P\rvert+\log N)$ after suitable preprocessing. Reporting all matches adds output cost.

Several classic results follow directly:

• Longest repeated substring: $\max_k\operatorname{LCP}[k]$. Adjacent suffixes suffice because all suffixes sharing a prefix form a contiguous interval.
• Number of distinct substrings: Begin with $N(N+1)/2$ substrings and subtract the prefixes already contributed by each suffix's predecessor.
• Longest common substring of two texts: Concatenate them with distinct sentinels, build one suffix array, and maximize LCP over adjacent suffixes originating in different texts. LCP values must not cross a separator.
• Repeated substring appearing at least $q$ times: Find the maximum of the minimum LCP over every window of $q$ consecutive suffixes.
• Lexicographically smallest rotation: Build the suffix array of $S+S$ with a sentinel and choose the first suffix start below $N$ whose first $N$ symbols form a rotation; Booth's algorithm is a simpler linear-time alternative for this single task.
• Substring comparison: Combine suffix ranks with an LCP query to compare two substrings after skipping their common prefix.