Optimal Square Detection Over General Alphabets
Jonas Ellert, Paweł Gawrychowski, Garance Gourdel · Society for Industrial and Applied Mathematics eBooks · 2023
Squares (fragments of the form xx, for some string x) are arguably the most natural type of repetition in strings. The basic algorithmic question concerning squares is to check if a given string of length n is square-free, that is, does not contain a fragment of such form. Main and Lorentz [J. Algorithms 1984] designed an