Suffix array and LCP

Sort all suffixes of a string, and for each pair of neighbouring suffixes find the longest common prefix with Kasai's method in O(n).

The suffix array lists the start positions of all suffixes of a string, sorted by the suffixes themselves. Every substring is a prefix of some suffix; so a binary search over the suffix array finds any pattern in O(m log n).

Read the full explanation ↓

Time: O(n² log n) to sort here (O(n log n) with doubling), O(n) for LCP
Space: O(n)
CLRS, section 32.5

Input:

S="banana"PDF export

banana; the sorted suffixes are a, ana, anana, banana, na, nana, with LCPs 0, 1, 3, 0, 0, 2.

def suffix_array(S):
n = len(S)
sa = sorted(range(n), key=lambda i: S[i:]) # the start positions, in the order of their suffixes
rows = [[sa[k], S[sa[k]:], "-"] for k in range(n)]
rank = [0] * n
for k in range(n):
rank[sa[k]] = k
# Kasai: going through the suffixes in text order, the common prefix shrinks by at most one each time.
h = 0
for i in range(n):
if rank[i] == 0:
h = 0
continue
j = sa[rank[i] - 1] # the suffix just before S[i:] in sorted order
while i + h < n and j + h < n and S[i + h] == S[j + h]:
h = h + 1
rows[rank[i]][2] = h
if h > 0:
h = h - 1
return sa

Invariant: If suffix i shares h characters with its neighbour, suffix i + 1 shares at least h − 1 with its own; so h never drops by more than one.

Start

012345

banana

h—

The table is still empty.

Local variables

S'banana'

Orange = changed in this step

Call stack

suffix_array()line 1

Step 1 of 64

Explanation

The idea

The LCP array

LCP[k] is the length of the longest common prefix of the k-th and (k−1)-th suffixes (in sorted order). Its largest value gives the longest repeated substring.

Kasai's method

Going through the suffixes in text order (not sorted order), the LCP drops by at most one each time; so h carries on from the previous value minus one, and the whole job is O(n).

What to watch in the trace

The table holds the sorted suffixes, and the LCP column fills in text order; the i and j pointers are the two suffixes being compared.