Sorting suffixes of twopattern strings
Abstract
Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar threestep approach, based on an initial division of the suffixes of x into two sets: in step 1 sort the first set using recursive reduction of the problem, in step 2 determine the order of the suffixes in the second set based on the order of the suffixes in the first set, and in step 3 merge the two sets together. To optimize such analgorithm either for space or time, it may not be sufficient to optimize one of the three steps, since in doing so, one might increase the resources required for the others to an unacceptable extent. Franek, Lu, and Smyth introduced twopattern strings as a generalization of Sturmian strings. Like Sturmian strings, twopattern strings are generated by iterated morphisms, but they exhibit a much richer structure. In this paper we show that the suffixes of twopattern strings can be sorted in linear time using a variant of the three step approach outlined above. It turns out that, given the order of the suffixes in a twopattern string, one can almost directly list in linear time all the suffixes of its expansion under a twopattern morphism.
Citation
Source Title
ISBN
Faculty
School
Collection
Related items
Showing items related by title, author, creator and subject.

Puglisi, Simon; Smyth, William; Yusufu, M. (2010)Given a string x = x[1..n] on an alphabet of size α, and a threshold p min ≥ 1, we describe four variants of an algorithm PSY1 that, using a suffix array, computes all the complete nonextendible repeats in x of length p ...

Antonitio, A.; Ryan, P.; Smyth, Bill; Turpin, A.; Yu, X. (2004)In 2003 three ()(n)time algorithms were proposed for the construction of a suffix array of a string x = x[1..n] on an indexed alphabet, all of them inspired by the methodology of Farach's ()(n) time suffix tree ...

Chen, G.; Puglisi, Simon; Smyth, B. (2008)For 30 years the LempelZiv factorization LZ x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) ...