Suffix Arrays, Prefix Doubling, and the Kasai LCP Scan

A suffix tree indexes every suffix of a text in linear space and answers “where does this pattern occur” in time proportional to the pattern length. It also carries a large constant: each node needs child pointers, edge labels, and a link, which on a 64-bit machine is dozens of bytes per character of text. A suffix array replaces the tree with a single permutation of the integers 0 to n−1, sorted by suffix, and recovers most of the tree’s queries with binary search. The memory difference is roughly an order of magnitude, and the queries are slower by a logarithmic factor unless the array is augmented with a second integer array.

What the permutation contains

For a text T of length n, the suffix array SA is a permutation such that the suffixes starting at SA[0], SA[1], …, SA[n−1] are in lexicographic order. The inverse permutation, the rank array, maps a starting position to its index in SA: rank[SA[i]] = i.

Every substring of T is a prefix of some suffix, and every occurrence of a pattern P is a suffix whose first |P| characters equal P. Since the array is sorted, those suffixes form a contiguous interval. Finding the interval is two binary searches, one for the first suffix not less than P and one for the first suffix greater than P, each comparing P against a suffix in O(|P|) time. The search costs O(|P| log n) character comparisons, or O(|P| + log n) with an LCP-aware search that uses the longest common prefix with the current bounds to skip characters already known to match.

The array alone answers occurrence counting, the lexicographic rank of a pattern among the text’s suffixes, and — with the LCP array — longest repeated substrings and distinct substring counts. It does not answer queries that need the tree’s topology, such as “the longest prefix of T[i..] that occurs at least k times elsewhere”, without additional structures.

Sorting suffixes by doubling

Sorting n suffixes naively costs O(n² log n) comparisons, and each comparison can cost O(n). The doubling method exploits the fact that a suffix is determined by its first character and the suffix that follows it: suffix i is the pair (T[i], suffix i+1). If suffixes are sorted by their first k characters, then sorting by the first 2k characters is sorting by the pair of ranks of the k-blocks starting at i and at i+k.

The construction keeps a rank array for k-blocks and doubles k each round:

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while k < n:
        # sort by (rank[i], rank[i+k]) with a sentinel rank of -1 past the end
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
        new = [0] * n
        for idx in range(1, n):
            a, b = sa[idx - 1], sa[idx]
            prev = (rank[a], rank[a + k] if a + k < n else -1)
            cur = (rank[b], rank[b + k] if b + k < n else -1)
            new[b] = new[a] + (cur != prev)
        rank = new
        if rank[sa[-1]] == n - 1:      # all ranks distinct: sorted
            break
        k *= 2
    return sa

The comparison sort above is O(n log n) per round, giving O(n log² n) overall. Replacing it with a two-pass radix sort on the pair of ranks, both in the range 0 to n−1, gives O(n) per round and O(n log n) overall. The pair is sorted by the second component first and the first component second, each with counting sort over n buckets. Ranks are integers, so counting sort applies directly; this is the reason the method uses ranks rather than characters.

The number of rounds is ⌈log₂ n⌉, because each round doubles the length of the prefix that is fully sorted, and after k exceeds n the ranks are the suffix order. The early exit is not cosmetic: on natural text, ranks usually become distinct after a few rounds, well before log n, because repeated prefixes of length 2^r are rare.

A suffix array of n integers costs 4n bytes with 32-bit entries, and the doubling construction needs two rank arrays, so peak memory is a small multiple of the text. The linear-time SA-IS algorithm removes the log factor by recursively sorting the induced order of a subset of suffixes, but it is substantially more intricate; which of the two a library ships is a matter of its size and speed targets rather than of any correctness requirement.

The LCP array and why it can be built in one pass

The LCP array stores, for each adjacent pair in SA, the length of their longest common prefix: LCP[k] = lcp(SA[k], SA[k+1]) for k from 0 to n−2, one entry shorter than SA. It is what turns the array into a usable index. Binary search with LCP bounds needs it, the longest repeated substring is its maximum, and the number of distinct substrings is derived from its sum.

Computing it by comparing each adjacent pair directly costs Θ(n²) on repetitive text, since each comparison can scan a long common prefix. Kasai’s observation removes the repetition: if suffix i has a common prefix of length h with its predecessor in SA, then suffix i+1 has a common prefix of length at least h−1 with its predecessor. Dropping the first character from both suffixes preserves the remaining h−1 characters as a common prefix, and the predecessor of suffix i+1 in sorted order is either that same suffix or something that shares at least as long a prefix.

The scan therefore proceeds in text order, carrying h forward and decreasing it by one between positions:

def kasai_lcp(s, sa):
    n = len(s)
    rank = [0] * n
    for idx, start in enumerate(sa):
        rank[start] = idx
    lcp = [0] * max(n - 1, 0)
    h = 0
    for i in range(n):
        r = rank[i]
        if r == 0:
            h = 0                 # no predecessor; the carried value is meaningless
            continue
        j = sa[r - 1]
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[r - 1] = h
        if h:
            h -= 1
    return lcp

The total work is linear because h increases only inside the while loop, and h decreases by at most one per iteration of the outer loop; over the whole scan h therefore increases by at most n times more than it decreases. Each increment is one character comparison, so the number of comparisons is O(n) even though a single iteration may scan a long common prefix. The bound is a sum over the whole scan, not a per-iteration limit.

Two details break naive implementations. The rank-0 case must reset h to zero, because there is no predecessor to compare against and carrying h from a previous position would be a lie about a suffix that has no left neighbour. And LCP is indexed by rank, not by text position: lcp[r−1] is the value for the pair ending at rank r, so an off-by-one here produces an array that looks plausible and is shifted by one entry.

Queries the pair answers directly

Longest repeated substring. Any substring that occurs twice is a common prefix of two suffixes, and the two suffixes are adjacent in the sorted order among all suffixes sharing that prefix. The longest repeated substring is therefore the maximum LCP value, and its length is that maximum. If overlapping occurrences are disallowed, the maximum must be taken over pairs whose starting positions differ by at least the LCP length, which requires a scan rather than a single maximum.

Number of distinct substrings. The total number of substrings, counting duplicates, is n(n+1)/2. Each distinct substring is a prefix of at least one suffix, and the suffixes contribute prefixes in sorted order; a suffix contributes exactly its length minus the longest prefix it shares with its predecessor, because every shorter prefix was already contributed. So the distinct count is

n(n+1)/2 − Σ LCP[i]

This identity is the basis for counting distinct substrings of a text without enumerating them, and it is the standard argument for why the LCP sum is the right quantity to maintain.

Longest common substring of two texts. Concatenate the texts with a separator that occurs in neither, build the suffix array of the concatenation, and take the maximum LCP over adjacent pairs whose starting positions lie on opposite sides of the separator. The separator must be a symbol outside the alphabet, not a byte that happens to be unused, or a suffix crossing the boundary can produce a false common prefix.

Occurrence intervals. The interval of suffixes sharing a prefix of length L can be found by expanding from a located occurrence while LCP values remain at least L, using a range-minimum structure over LCP for the expansion. With a sparse table over LCP, the range minimum is O(1) after O(n log n) preprocessing; with a segment tree it is O(log n) with O(n) memory.

Where the array is the wrong index to build

The suffix array is static. Inserting text or deleting a prefix requires rebuilding or using a dynamic structure; the sorted order of suffixes changes globally when a character is inserted near the front. Texts that grow incrementally are better served by the suffix automaton, which supports appending a character in amortised constant time and answers distinct-substring and occurrence queries online.

Building the array costs O(n log n) time and a multiple of n memory even for a single query. For one-off searches of a pattern in a text, the prefix function or Boyer–Moore needs O(m) memory and no preprocessing of the text at all. The suffix array earns its cost when many queries hit the same text, which is the situation in full-text search and in the Burrows–Wheeler index built on top of the same ordering.

A last constraint is the alphabet and the sentinel. Doubling assumes characters compare as integers, which holds for bytes and code points but not for collated text where case and accent folding change the order. And the sentinel convention — a unique smallest symbol appended to the text — simplifies the construction and the LCP bounds but must not be a value that can appear in the input; with byte text, appending a zero byte is safe only if the text is not permitted to contain one.