SQUARES, CUBES, AND TIME-SPACE EFFICIENT STRING SEARCHING

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 parameter k on which the complexity depends and that orginally satisifies k greater-than-or-equal-to 4. We show that k = 3 is the least integer for which the GS algorithm works. This value of the parameter k also minimizes the time of the search phase of the string-searching algorithm. With the parameter k = 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 length n starts by less than log(THETA) 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.