A note on easy and efficient computation of full abelian periods of a word (Q313772): Difference between revisions

The Parikh vector \(\mathcal{P}_{w}\) of a word \(w\) is the vector whose \(i\)-th entry is the number of occurrences in \(w\) of the \(i\)-th letter of the alphabet. Two words \(x\), \(y\) are commutatively equivalent if \(\mathcal{P} _{x}=\mathcal{P}_{y}\). For two words \(x\), \(y\), \(\mathcal{P}_{x}\subset \mathcal{P}_{y}\) if \(\left| x\right| <\left| y\right| \) and no entry in \(\mathcal{P}_{x}\) is greater than the corresponding entry in \(\mathcal{P}_{y}\). An integer \(p>0\) is an abelian period of a word \(w\) if \(w=u_{0}u_{1}\cdots u_{k-1}u_{k}\) where, for \(0<i<k\), all the factors \(u_{i}\) are pairwise commutatively equivalent, and \(\mathcal{P}_{u_{0}}\subset\mathcal{P}_{u_{1} },\mathcal{P}_{u_{k}}\subset\mathcal{P}_{u_{1}}\). The words \(u_{0}\) and \(u_{k}\) are called the head and the tail of the abelian period \(p\), respectively. A word can have several different abelian periods. An abelian period is called full if both the head and the tail are empty. The paper presents a \(O(n\log\log n)\)-time algorithm for computing all the full abelian periods of a word of length \(n\) over a constant-size alphabet. The authors' experiments document that, for problems of reasonable size, despite its higher asymptotic complexity, this algorithm significantly outperforms the \(O(n)\) algorithm of \textit{T. Kociumaka} et al. [J. Comput. Syst. Sci. 84, 205--218 (2017; Zbl 1353.68225)].