Fast algorithms for Abelian periods in words and greatest common divisor queries
详细信息 查看全文
- 作者：T. Kociumaka kociumaka@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author ; J. Radoszewski ; jrad@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author ; W. Rytter rytter@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author
- 关键词：Abelian period ; Jumbled pattern matching ; Greatest common divisor
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：205-218
- 全文大小：461 K
文摘
- •
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.