Induced Suffix Sorting for String Collections
Felipe Alves da Louza, Simon Gog, Guilherme Pimentel Telles · 2016
Sorting all suffixes of a string collection may be performed by sorting the concatenation of all strings using different end marker symbols as separators, or alternatively using the same end marker as separator. However, both approaches have the following drawbacks. The first alternative increases the alphabet size of the resulting string by the number of strings, whereas the second alternative does not guarantee the order among suffixes that are equal up to the end marker symbol. In this article, we show how to modify two important suffix sorting algorithms, SAIS [1] and SACA-K [2], to sort the concatenated string using the same end marker, maintaining their theoretical bounds, respecting the order among all suffixes, and improving their practical performance.