Algorithms for computing abelian periods of words

DOI10.1016/J.DAM.2013.08.021zbMATH Open1329.68197arXiv1211.5389OpenAlexW2026696944MaRDI QIDQ496544FDOQ496544

Authors: Gabriele Fici, Thierry Lecroq, A. Lefebvre, Élise Prieur-Gaston 

Publication date: 22 September 2015

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

Abstract: Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $sigma$ can have $Theta(n^2)$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^{2}imessigma)$ using $O(nimessigma)$ space. We present an off-line algorithm based on a $sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.

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

Recommendations

• A note on easy and efficient computation of full abelian periods of a word
• Fast computation of abelian runs
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Online computation of abelian runs
• Fast algorithms for abelian periods in words and greatest common divisor queries

zbMATH Keywords

combinatorics on wordsabelian perioddesign of algorithmstext algorithmsweak repetitionabelian repetition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abelian Repetitions in Sturmian Words
• Algorithms for jumbled pattern matching in strings
• Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On approximate jumbled pattern matching in strings
• Binary jumbled string matching for highly run-length compressible texts
• Indexing permutations for binary strings
• New algorithms for binary jumbled pattern matching

Cited In (13)

• On highly palindromic words: the \(n\)-ary case
• Abelian periods of factors of Sturmian words
• String Periods in the Order-Preserving Model
• Abelian Repetitions in Sturmian Words
• Computing regularities in strings: a survey
• Dyck Words, Lattice Paths, and Abelian Borders
• A note on easy and efficient computation of full abelian periods of a word
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Title not available (Why is that?)
• Title not available (Why is that?)
• String periods in the order-preserving model
• Abelian-primitive partial words
• Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

This page was built for publication: Algorithms for computing abelian periods of words

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