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:
*Subscription may be required


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
Item Control Page Item Control Page