zbMATH — the first resource for mathematics

Squares, cubes, and time-space efficient string searching. (English) Zbl 0849.68044
Summary: 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 originally satisfies \(k\geq 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_\Phi 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 Z. Galil and J. Seiferas [J. Comput. System Sci. 26, 280-294 (1983; Zbl 0509.68101)] 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.

68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
68W15 Distributed algorithms
68R15 Combinatorics on words
PDF BibTeX Cite
Full Text: DOI
[1] A. V. Aho, Algorithms for finding patterns in strings, in: J. van Leeuwen, ed.Handbook of Theoretical Computer Science, vol. A, Elsevier, Amsterdam, 1990, pp. 255-300. · Zbl 0900.68249
[2] M. Crochemore, String-matching on ordered alphabets,Theoret. Comput. Sci. 92 (1992), 33-47. · Zbl 0747.68021
[3] M. Crochemore and D. Perrin, Two-way string-matching,J. Assoc. Comput. Mach. 38(3) (1991), 651-675. · Zbl 0808.68063
[4] Z. Galil and J. Seiferas, Saving space in fast string matching,SIAM J. Comput. 9 (1980), 417-438. · Zbl 0446.68041
[5] Z. Galil and J. Seiferas, Time-space optimal string matching,J. Comput. System Sci. 26 (1983), 280-294. · Zbl 0509.68101
[6] A. Gibbons and W. Rytter,Efficient Parallel Algorithms, Cambridge University Press, Cambridge, 1988. · Zbl 0771.68015
[7] D. E. Knuth, J. H. Morris, Jr., and V. R. Pratt, Fast pattern matching in strings,SIAM J. Comput. 6 (1977), 323-350. · Zbl 0372.68005
[8] M. Lothaire,Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
[9] I. Simon, Personal communication, 1989.
[10] U. Vishkin, Optimal parallel pattern matching in strings,Inform. and Control 67 (1985), 91-113. · Zbl 0588.68023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.