Squares, cubes, and time-space efficient string searching
Squares, cubes, and time-space efficient string searching
复制标题
平方、立方体和时空有效的字符串搜索
作者：
M. Crochemore;W. Rytter
我们解决了与Galil和Seiferas的时间间隔最佳字符串匹配算法有关的几个技术问题（称为GS算法）。 GS算法的最小整数也可以最大程度地减少字符串搜索算法的搜索阶段。考虑在线性时间和对数空间中的更简单的算法。前缀正方形和立方体的组合对于使用小内存匹配是必不可少的。 GS算法。以后的算法在[GS2]中给出的算法，我们提出了一种最佳的平行算法，以进行模式预处理。
We address several technical problems related to the time-space optimal string-matching algorithm of Galil and Seiferas (called the GS algorithm). This algorithm contains a parameterk on which the complexity depends and that originally satisfiesk ≥ 4. We show thatk=3 is the least integer for which the GS algorithm works. This value of the parameterk also minimizes the time of the search phase of the string-searching algorithm. With the parameterk=2 we consider a simpler version of the algorithm working in linear time and logarithmic space. This algorithm is based on the following fact: any word of lengthn starts by less than logΦn squares of primitive prefixes. Fibonacci words have a logarithmic number of square prefixes. Hence, the combinatorics of prefix squares and cubes is essential for string-matching with small memory.We give a time-space optimal sequential computation of the period of a word based on the GS algorithm. The latter corrects the algorithm given in [GS2] for the computation of periods. We present an optimal parallel algorithm for pattern preprocessing. This paper also provides a cleaner version and a simpler analysis of the GS algorithm.