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