SQUARES, CUBES, AND TIME-SPACE EFFICIENT STRING SEARCHING

We address several technical problems related to the time-space optima l string-matching algorithm of Galil and Seiferas (called the GS algor ithm). This algorithm contains a parameter k on which the complexity d epends 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 p hase of the string-searching algorithm. With the parameter k = 2 we co nsider a simpler version of the algorithm working in linear time and l ogarithmic space. This algorithm is based on the following fact: any w ord 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 fo r string-matching with small memory. We give a time-space optimal sequ ential computation of the period of a word based on the GS algorithm. The latter corrects the algorithm given in [GS2] for the computation o f periods. We present an optimal parallel algorithm for pattern prepro cessing. This paper also provides a cleaner version and a simpler anal ysis of the GS algorithm.