Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Sorting suffixes of two-pattern strings

Franěk, F. and Smyth, W.F. (2005) Sorting suffixes of two-pattern strings. International Journal of Foundations of Computer Science, 16 (6). pp. 1135-1144.

Link to Published Version:
*Subscription may be required


Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: Step 1 sorts the first set using recursive reduction of the problem, Step 2 determines the order of the suffixes in the second set based on the order of the suffixes in the first set, and Step 3 merges the two sets together. To optimize such an algorithm 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 two-pattern strings as a generalization of Sturmian strings. Like Sturmian strings, two-pattern strings are generated by iterated morphisms, but they exhibit a much richer structure. In this paper we show that the suffixes of two-pattern strings can be sorted in linear time using a variant of the three-step approach outlined above, but without the need for recursion. It turns out that, given the order of the suffixes in a two-pattern string, one can almost directly list in linear time all the suffixes of its expansion under a two-pattern morphism.

Item Type: Journal Article
Publisher: World Scientific Publishing Co.
Item Control Page Item Control Page