Optimal Square Detection Over General Alphabets

Jonas Ellert, Paweł Gawrychowski, Garance Gourdel

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…