Extracting powers and periods in a word from its runs structure (Q389938)

As the authors note in the abstract, the applications of runs (the maximal periodic subwords) in a word are underrepresented in the existing literature, and this paper tries to fill in this gap. The results are related to {\parindent=4mm \begin{itemize}\item[--] the decomposition into pairwise disjoint classes of sets of runs of a given word, based on Lyndon-roots; \item[--] computing and listing in linear time the \(k\)-th powers in a given word; and \item[--] computing by a formula the number of occurrences of a \(k\)-th power in a given word; and \item[--] computing in linear time all local periods of a word. \end{itemize}} Efficient algorithms for testing primitivity of subwords and computing primitive roots are given too.