DSA Suffix Structures, Surveyed

A suffix array lists the starting positions of a string's suffixes in sorted order. A suffix is the tail of the string that begins at one position and runs to the end.

The suffixes of banana

Each line starts one position later than the line before. The last suffix is a single letter.

word = "banana"
for start in range(len(word)):
    print(start, word[start:])

Sorted into an array

The array stores starting positions, not the suffix strings themselves. Reading the positions in array order reads the suffixes alphabetically.

def suffix_array(word):
    return sorted(range(len(word)), key=lambda start: word[start:])


word = "banana"
starts = suffix_array(word)
print("Suffix array:", starts)
for start in starts:
    print(start, word[start:])

The LCP table

The first LCP entry is 0 by convention, since no neighbour stands before it. The entry 3 records that ana and anana share three opening letters.

def suffix_array(word):
    return sorted(range(len(word)), key=lambda start: word[start:])


def lcp_length(a, b):
    count = 0
    while count < len(a) and count < len(b) and a[count] == b[count]:
        count += 1
    return count


word = "banana"
starts = suffix_array(word)
lcp = [0]
for rank in range(1, len(starts)):
    left = word[starts[rank - 1]:]
    right = word[starts[rank]:]
    lcp.append(lcp_length(left, right))
print("Suffix array:", starts)
print("LCP table:", lcp)

Example

def suffix_array(word):
    return sorted(range(len(word)), key=lambda start: word[start:])


def lcp_length(a, b):
    count = 0
    while count < len(a) and count < len(b) and a[count] == b[count]:
        count += 1
    return count


word = "banana"
starts = suffix_array(word)
print("Word:", word)
print("Suffix array:", starts)
previous = None
for rank, start in enumerate(starts):
    suffix = word[start:]
    if previous is None:
        shared = 0
    else:
        shared = lcp_length(previous, suffix)
    print("Rank", rank, "start", start, "suffix", suffix, "lcp", shared)
    previous = suffix
print("Suffixes:", len(starts))

Key points

Sorting the suffixes groups every group of strings that share an opening together
LCP means longest common prefix, measured here between neighbouring suffixes in the sorted order
The LCP table shows how much each suffix shares with the one ranked just before it
Equal neighbours in the LCP table expose repeated substrings of the original string
A suffix tree and a suffix automaton answer harder suffix questions, and both are named here as the road beyond

In this example, the six suffixes of banana are ranked one per line. Each line prints the rank, the starting position, the suffix itself, and its LCP against the previous line. The tallest LCP is 3, between ana and anana. Suffix trees and suffix automata build on this same sorted order to answer substring questions faster.

Note

This lesson builds the array by sorting directly, which suits short strings and learning the shape

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def suffix_array(word):
    return sorted(range(len(word)), key=lambda start: word[start:])


def lcp_length(a, b):
    count = 0
    while count < len(a) and count < len(b) and a[count] == b[count]:
        count += 1
    return count


word = "banana"
starts = suffix_array(word)
print("Word:", word)
print("Suffix array:", starts)
previous = None
for rank, start in enumerate(starts):
    suffix = word[start:]
    if previous is None:
        shared = 0
    else:
        shared = lcp_length(previous, suffix)
    print("Rank", rank, "start", start, "suffix", suffix, "lcp", shared)
    previous = suffix
print("Suffixes:", len(starts))

Exercise

In the suffix array of banana, which suffix stands at rank 0?

banana anana a nana