A note on easy and efficient computation of full abelian periods of a word

DOI10.1016/J.DAM.2015.09.024MaRDI QIDQ313772zbMATH OpenOpenAlexFDO

Authors Gabriele Fici, Thierry Lecroq, A. Lefebvre, Élise Prieur-Gaston, W. F. Smyth

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00634

zbMATH Keywords

abelian powertext algorithmsfull abelian periodweak repetition

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(nloglogn)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.

Recommendations

• Online computation of abelian runs
• Fast computation of abelian runs
• Algorithms for computing abelian periods of words
• An abelian periodicity lemma
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Inferring strings from full abelian periods
• A note on efficient computation of all abelian periods in a string
• \(k\)-abelian pattern matching

Cites work

• scientific article; zbMATH DE number 5605094 (Why is no real title available?)
• scientific article; zbMATH DE number 1052825 (Why is no real title available?)
• A note on efficient computation of all abelian periods in a string
• Algorithm and bound for the greatest common divisor of n integers
• Algorithms for computing abelian periods of words
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Identifying all abelian periods of a string in quadratic time and relevant problems

Cited in

(11)

• String Periods in the Order-Preserving Model
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Algorithms for computing abelian periods of words
• Fast computation of abelian runs
• String periods in the order-preserving model
• Online computation of abelian runs
• Inferring strings from full abelian periods
• Identifying all abelian periods of a string in quadratic time and relevant problems
• A note on efficient computation of all abelian periods in a string
• Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

This page was built for publication: A note on easy and efficient computation of full abelian periods of a word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313772)