Journal article
Prefix table construction and conversion
Combinatorial Algorithms, Vol.8288, pp.41-53
2013
Abstract
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.
Details
- Title
- Prefix table construction and conversion
- Authors/Creators
- W. Bland (Author/Creator) - McMaster-CarrG. Kucherov (Author/Creator) - Laboratoire d'Informatique Gaspard-MongeW.F. Smyth (Author/Creator) - The University of Western Australia
- Publication Details
- Combinatorial Algorithms, Vol.8288, pp.41-53
- Publisher
- Springer Verlag
- Identifiers
- 991005545019607891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
44 Record Views