Catalog Home Page

Prefix table construction and conversion

Bland, W., Kucherov, G. and Smyth, W.F. (2013) Prefix table construction and conversion. Lecture Notes in Computer Science, 8288 . pp. 41-53.

Link to Published Version: http://dx.doi.org/10.1007/978-3-642-45278-9_5
*Subscription may be required

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.

Publication Type: Journal Article
Publisher: Springer Verlag
URI: http://researchrepository.murdoch.edu.au/id/eprint/28235
Item Control Page Item Control Page