Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Prefix Table Construction and Conversion
verfasst von : Widmer Bland, Gregory Kucherov, W. F. Smyth
Erschienen in: Combinatorial Algorithms
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
The
prefix table
of a string
x
=
x
[1..
n
] is an array
π
=
π
[1..
n
] such that
π
[
i
] is the length of the longest substring beginning at
i
that equals a prefix of
x
. In this paper we describe and evaluate algorithms for prefix table construction, some previously proposed, others designed by us. We also describe and evaluate new linear-time algorithms for transformations between
π
and the
border array
.