Prefix Table Construction and Conversion

International audienceThe 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 algorithms for the conversions π ↔ β, where β[1..n] is the well-known border array