Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries

摘要

We present efficient algorithms computing all Abelian periods of two types in a word. Regular Abelian periods are computed in O(n log log{n}) randomized time which improves over the best previously known algorithm by almost a factor of n. The other algori