dc.contributor.author Franek, F. dc.contributor.author Smyth, Bill dc.contributor.editor Milan Simanek dc.contributor.editor Jan Holub dc.date.accessioned 2017-01-30T11:56:04Z dc.date.available 2017-01-30T11:56:04Z dc.date.created 2010-04-01T20:02:07Z dc.date.issued 2004 dc.identifier.citation Franek, Frantisek and Smyth, W. 2004. Sorting suffixes of two-pattern strings, in Simanek, M. and Holub, J. (ed), Prague Stringology Conference, pp. 69-78. Prague. Czech Republic: Vydavatelstvi CVUT. dc.identifier.uri http://hdl.handle.net/20.500.11937/16490 dc.description.abstract 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: 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 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. 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. dc.publisher Vydavatelstvi CVUT dc.title Sorting suffixes of two-pattern strings dc.type Conference Paper dcterms.source.startPage 69 dcterms.source.endPage 78 dcterms.source.title Proceedings of the Prague Stringology Conference dcterms.source.series Proceedings of the Prague Stringology Conference dcterms.source.isbn 80-01-03050-4 dcterms.source.conference Prague Stringology Conference dcterms.source.conference-start-date Aug 30 2004 dcterms.source.conferencelocation Prague, Czech Republic dcterms.source.place Czech Republic curtin.department Digital Ecosystems and Business Intelligence Institute (DEBII) curtin.accessStatus Open access curtin.faculty Curtin Business School curtin.faculty The Digital Ecosystems and Business Intelligence Institute (DEBII)
﻿