Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
In-Place Suffix Sorting
verfasst von : Gianni Franceschini, S. Muthukrishnan
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given string
T
=
T
[1,...,
n
], the
suffix sorting
problem is to lexicographically sort the suffixes
T
[
i
,...,
n
] for all
i
. This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of
workspace
needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant
c
in the
O
(
n
) =
cn
space algorithms known for this problem,
Currently the best previous result [5] takes
time and
extra space, for any
$v\in [1,\sqrt{n}]$
for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes
time using
O
(1) workspace and is optimal in the worst case for the general alphabet.