Suffix array

Build a sorted suffix array.

Suffix array

A suffix array is the alphabetically sorted list of starting indices of all suffixes of a string. For "banana" we get [5, 3, 1, 0, 4, 2] after sorting suffixes.

Suffix arrays are used in large-text search, longest repeated substring and compression. A pattern can be searched in O(m log n) with binary search.

Direct sorting takes O(n² log n); efficient algorithms reach O(n log n).

Suffix array construction

The simplest construction is to generate all suffixes and sort them with Python's sort. Each suffix is stored as a tuple (string, index).

After sorting we keep only the indices. This method is O(n² log n); sufficient for small strings.

At an advanced level, comparing prefix pairs reduces this to O(n log² n).

Exercise build_suffix_array function

Write build_suffix_array(s). Return the sorted suffix indices. Print [5, 3, 1, 0, 4, 2] with print(build_suffix_array("banana")).

Show example solution

def build_suffix_array(s):
    # Sorted suffix indices
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort(key=lambda x: x[0])
    return [idx for _, idx in suffixes]
print(build_suffix_array("banana"))

Test yourself

suffix list

suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[____])

Show answer

suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])

Suffix array concepts

suffix

Substring starting at i
sorted

Alphabetical order
binary search

O(m log n)
index

Start position
What does a suffix array store?
```
sa = [5, 3, 1, 0, 4, 2]
```
- Character codes of the string
- Start indices of sorted suffixes
- The suffix strings themselves
- Lengths of the suffixes
Show answer

Start indices of sorted suffixes — A suffix array stores start indices of sorted suffixes.

Next lesson: Summary - String matching

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies