IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS

DOI10.1142/S0129054112500190zbMath1266.68147arXiv1201.6162WikidataQ61677871 ScholiaQ61677871MaRDI QIDQ4923285

Maxime Crochemore, Costas S. Iliopoulos, Michalis Christou

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithms; strings; abelian periods

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R15: Combinatorics on words

Related Items

Abelian Repetitions in Sturmian Words, A note on easy and efficient computation of full abelian periods of a word, Weak abelian periodicity of infinite words, Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings, On highly palindromic words: the \(n\)-ary case, Abelian borders in binary words

Cites Work

• Unnamed Item
• Efficient detection of quasiperiodicities in strings
• On shortest crucial words avoiding abelian powers
• A cyclic binary morphism avoiding abelian fourth powers
• An on-line string superprimitivity test
• Some logical characterizations of the dot-depth hierarchy and applications
• Efficient Seeds Computation Revisited
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Fast Pattern Matching in Strings
• Prime sieves using binary quadratic forms
• Computing the cover array in linear time