Suffix Arrays & the Longest Repeat
In short: a suffix array is every suffix of a string, sorted alphabetically — stored as just their starting indices, not copies of the text. Once sorted, two suffixes that share a long prefix sit next to each other, because sorting groups anything alike. The LCP array (longest common prefix) measures exactly how much each neighbouring pair shares. Together they turn "does this substring repeat, and how much" from a scan-everything question into a read-the-neighbours question.
Sorting suffixes instead of comparing substrings
"banana" has 6 suffixes: banana, anana, nana, ana, na, a.
Sorted alphabetically:
The array stores indices, [5, 3, 1, 0, 4, 2], not the suffix strings
themselves — slicing s[i:] is only for printing. Building it this way, by
sorting Python string slices, is O(n² log n) in the worst case (each
comparison can itself cost O(n)), fine for a lesson-sized string; production
suffix-array builders use O(n log n) radix-style construction, which is
past this lesson's scope.
The LCP array: what sorting buys you
Walk the sorted list and measure how much each suffix shares with the one right before it:
The 3 is ana and anana sharing ana — the longest repeated
substring in "banana" is sitting in that one gap, found without ever
comparing two suffixes that aren't neighbours in the sorted order. Any
repeated substring of length k means two suffixes that agree on their
first k characters — and sorting has already put every pair that agrees
on anything as close together as possible.
banana's six suffixes, sorted, with each one's LCP against its LEFT neighbour as the label underneath. The 3 between ana and anana is the longest repeat.
a and ana share 1 letter: a. 6 cells. Comparing a and ana.
Quick practice
def suffix_array(s):
n = len(s)
return sorted(range(n), key=lambda i: s[i:])
print(suffix_array("abab"))IndexErrorThis crashes with an IndexError the moment two suffixes match all the way to the end of the shorter one. Add the missing length guards.
What it costs
| operation | cost | why |
|---|---|---|
| naive suffix array (sort string slices) | O(n² log n) worst case | each comparison can itself take O(n), and there are n log n comparisons |
| LCP array from a built suffix array | O(n²) worst case (naive), O(n) with Kasai's algorithm | this lesson uses the naive version; Kasai's is a fast-follow, not covered here |
| longest repeated substring, once both arrays exist | O(n) | one scan for the max LCP |
| the naive "compare every pair of substrings" approach | O(n³) or worse | no sorting, no shared structure to exploit |
🎯 Your turn
Build longest_repeated_substring(s): the longest substring of s that
occurs more than once (overlapping occurrences count), using a suffix array
and an LCP array. Return "" if nothing repeats.
longest_repeated_substring("banana")→"ana"longest_repeated_substring("abcabcabc")→"abcabc"longest_repeated_substring("abcd")→""
Hint: build the suffix array, build the LCP array from it, then the answer is the suffix at the position of the maximum LCP value, sliced to that LCP's length.
Press ▶ Run, then ✓ Check.