scientific article; zbMATH DE number 3913712

From MaRDI portal
Publication:3690246





[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.




Cited in
(37)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3690246)