The problem
Return a pair (sa, lcp). sa is the suffix array of s: the places 0 .. n − 1 in the alphabetical order of the suffixes s[i:] that start there. lcp[r], for r ≥ 1, is the length of the longest common prefix (shared start) of the suffixes in rows r − 1 and r; lcp[0] is 0.
suffix_lcp("banana")
# ([5, 3, 1, 0, 4, 2], [0, 1, 3, 0, 0, 2])
suffix_lcp("aaaa")
# ([3, 2, 1, 0], [0, 1, 2, 3])
The string has at least one lower-case letter. A shorter suffix comes before a longer one that starts with it, as in Python’s own string order.
Limits
- Up to 100,000 letters. The big tests have 5 seconds each.
- Sorting with
key=lambda i: s[i:]copies every suffix (5 billion letters for 100,000 of one letter), and comparing two neighbouring rows from scratch is O(n²) there.sortedand.sort()are allowed.
Builds on STRG-5 Suffix arrays.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | banana | Not run | |
| 2 | One letter | Not run | |
| 3 | A run | Not run | |
| 4 | All different | Not run | |
| 5 | mississippi | Not run | |
| 6 | Repeats | Not run | |
| 7 | 100,000 of one letter | Not run | |
| 8 | 100,000 random letters | Not run | |
| 9 | Two letters, 100,000 | Not run | |
| 10 | The Fibonacci word | Not run |