Efficient representation and counting of antipower factors in words (Q5919279)

A \textit{\(k\)-antipower} (for \(k\geq 2\)) is a concatenation of \(k\) distinct words of the same length (called \textit{antiperiod}). It is known that a word of length \(n\) can have \(\Theta(n^2/k)\) antipower fragments, and they can all be reported in \(O(n^2/k)\) time. In particular, all \(k\)-antipower fragments of a specified antiperiod \(d\) can be reported in \(O(n)\) time. The authors present several results on the algorithmic problem of locating and reporting antipower fragments of an input word of length \(n\) over an integer alphabet \(\{1,...,n^{O(1)}\}\). The first result is an algorithm that computes the number \(C\) of \(k\)-antipower fragments in \(O(nk \log k)\) time and reports them in \(O(nk \log k + C )\) time. The second result is an algorithm that computes the number of different factors that are \(k\)-antipowers in \(O(nk^4 \log k \log n)\) time. The third result is a construction in \(O(n^2/r)\) time of a data structure of size \(O(n^2/r)\), for any \(r \in \{1,...,n\}\), which answers antipower queries in \(O(r)\) time. Thus, any \(n\) antipower queries can be answered in \(O(n\sqrt{n})\) time and space.