Linear time recognition of squarefree strings. (English) Zbl 0572.68068

Main, Michael G.; Lorentz, Richard J.

Combinatorial algorithms on words, Proc. NATO Adv. Res. Workshop, Maratea/Italy 1984, NATO ASI Ser., Ser. F 12, 271-278 (1985).

[For the entire collection see Zbl 0564.00027.]
A square is an immediately repeated nonempty string, e.g., aa, abab, abcabc. This paper presents a new O(n log n) algorithm to determine whether a string of length n has a substring which is a square. The algorithm is not as general as some previous algorithms for finding all squares, but it does have a simplicity which the others lack. Also, for a fixed alphabet of size k, the algorithm can be improved by a factor of \(\log_ k(n)\), yielding an O(n) algorithm for determining whether a string contains a square.

MSC:

68Q45

Formal languages and automata

Keywords:

linear time algorithm; square

Citations:

Zbl 0564.00027