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 as. 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.
展开▼
机译：字符串x = x [1..n]的前缀表是一个数组π=π[1..n]，这样π[i]是从i开始的最长子字符串的长度，它等于as的前缀。在本文中，我们描述和评估了用于前缀表构建的算法，其中一些算法是先前提出的，其他是我们设计的。我们还将描述和评估用于π和边界数组之间转换的新线性时间算法。
展开▼
