Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item Type: Journal Article
Publisher: Springer Verlag
Item Control Page Item Control Page