In “Find the Longest Repeat in a String”¹, we saw that suffix trees can be too memory intensive to apply in practice.

In 1993, Udi Manber and Gene Myers introduced suffix arrays as a memory-efficient alternative to suffix trees. To construct SuffixArray(Text), we first sort all suffixes of Text lexicographically, assuming that "$" comes first in the alphabet. The suffix array is the list of starting positions of these sorted suffixes. For example,

Assignment

Implement the generate_suffix_array method which takes a string. The end-of-string marker "$" is not part of this string and should be appended.

The function should return the constructed suffix array in the form of a tuple of len(string + "$") indices.

Example

>>> generate_suffix_array('ACACTTTCGA')
(10, 9, 0, 2, 1, 7, 3, 8, 6, 5, 4)