Suffix Array

A sorted array of all suffix starting positions of a string, giving compact full-text indexing and fast substring search.

Definition

The suffix array of a string S is the permutation of positions 0..n-1 that lists all suffixes of S in lexicographic order. Together with the string it supports substring search by binary search in O(m log n) for a pattern of length m, and it uses far less memory than a suffix tree.

Construction

A naive sort of n suffixes costs O(n^2 log n) from comparisons. The prefix-doubling method sorts suffixes by their first 2^k characters using ranks from the previous round, reaching O(n log n) or O(n log^2 n). Linear-time algorithms exist: DC3/skew and SA-IS, the latter being the practical standard.

LCP array

The longest-common-prefix (LCP) array stores, for each adjacent pair in the sorted order, the length of their shared prefix. Kasai's algorithm builds it in O(n). With the LCP array, the suffix array answers many queries a suffix tree can: number of distinct substrings, longest repeated substring, and pattern counting.

# prefix doubling (O(n log^2 n))
def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i+k] if i+k < n else -1)
        sa.sort(key=key)
        tmp = [0]*n
        for j in range(1, n):
            tmp[sa[j]] = tmp[sa[j-1]] + (key(sa[j]) > key(sa[j-1]))
        for i in range(n):
            rank[i] = tmp[i]
        if rank[sa[-1]] == n-1:
            break
        k *= 2
    return sa

Uses

• Full-text substring search and counting occurrences.
• Longest repeated and longest common substring via the LCP array.
• The Burrows-Wheeler transform and FM-index build on suffix arrays for compressed search.