Fast algorithms for Abelian periods in words and greatest common divisor queries

作者：

Highlights：

• We present a linear-time algorithm computing all full Abelian periods of a word.

• We show fast randomized and deterministic algorithms computing all Abelian periods.

• We obtain O(1)-time GCD queries with arguments at most n with O(n) preprocessing time.

摘要

•We present a linear-time algorithm computing all full Abelian periods of a word.•We show fast randomized and deterministic algorithms computing all Abelian periods.•We obtain O(1)-time GCD queries with arguments at most n with O(n) preprocessing time.

论文关键词：Abelian period,Jumbled pattern matching,Greatest common divisor

论文评审过程：Received 24 June 2014, Revised 31 August 2016, Accepted 11 September 2016, Available online 12 October 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.09.003