Suffix Arrays
SA[i] = starting position of the i-th lexicographically smallest suffix. Space-efficient alternative to suffix trees (just an int array).
Example: "banana$"
SA = [6, 5, 3, 1, 0, 4, 2]
SA[0]=6 -> "$"
SA[1]=5 -> "a$"
SA[2]=3 -> "ana$"
SA[3]=1 -> "anana$"
SA[4]=0 -> "banana$"
SA[5]=4 -> "na$"
SA[6]=2 -> "nana$"
Naive Construction — O(n^2 log n)
def build_suffix_array_naive(text):
"""Sort all suffixes. O(n^2 log n) due to O(n) string com
[Description truncada. Veja o README completo no GitHub.]