Suffix array
- Algorithms course
- Expert
- Lesson 17/41
- 4 min
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).
Practice 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")).
Starter code
def build_suffix_array(s):
# Sorted suffix indicesSample 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"))Expected output
[5, 3, 1, 0, 4, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 suffix list
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[____])suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])Explanation: Sorted by the suffix string.
2 Suffix array concepts
| Term | Meaning |
|---|---|
suffix |
Substring starting at i |
sorted |
Alphabetical order |
binary search |
O(m log n) |
index |
Start position |
3 What does a suffix array store?
sa = [5, 3, 1, 0, 4, 2]- Character codes of the string
- Start indices of sorted suffixes Correct answer
- The suffix strings themselves
- Lengths of the suffixes
Explanation: A suffix array stores start indices of sorted suffixes.