Algorithms for anti-powers in strings (Q1641162)

A concatenation of \(k\) identical copies of a string of length \(m\) is a power of order \(k\) (or \(k\)-power); the integer \(m\) is its period. A concatenation of \(k\) pairwise-distinct strings of identical length \(m\) is an anti-power of order \(k\) (or \(k\)-anti-power); the integer \(m\) is its anti-period. The authors show that every string of length \(n\) contains \(\Omega\left( n^{2}/k\right) \) anti-powers of order \(k\), and they provide an algorithm that finds, for a given string \(S\) of length \(n\), the locations of all substrings of \(S\) that are \(k\)-anti-powers. The algorithm is optimal since it works in \(O(n^{2}/k)\) time and \(O(n)\) space.