Construction of Suffix Arrays
Suffix Arrays for Competitive Programming
A suffix array is a sorted array of all suffixes of a given string. More formally if you are given a string ‘S’ then the suffix array for this string contains the indices 0 to n, such that the suffixes starting from these indices are sorted lexicographically.
Example:
Input: banana
0 banana 5 a
1 anana Sort the Suffixes 3 ana
2 nana —————-> 1 anana
3 ana alphabetically 0 banana
4 na 4 na
5 a 2 nanaSo the suffix array for “banana” is {5, 3, 1, 0, 4, 2}