Efficient enumeration of non-equivalent squares in partial words with few holes

DOI10.1007/s10878-018-0300-zzbMath1445.68364OpenAlexW2731625863WikidataQ61677816 ScholiaQ61677816MaRDI QIDQ5971176

Maxime Crochemore, Jakub Radoszewski, Tomasz Walen, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Wojciech Rytter, Tomasz Kociumaka

Publication date: 6 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01787563/file/squares_partial.pdf

zbMATH Keywords

holepartial wordLyndon wordLyndon rootapproximate periodsquare factorsquare in a word

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• The three-squares lemma for partial words with one hole
• How many double squares can a string contain?
• An algorithmic toolbox for periodic partial words
• How many squares can a string contain?
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Squares, cubes, and time-space efficient string searching
• Squares and primitivity in partial words
• Squares in partial words
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• Computing Primitively-Rooted Squares and Runs in Partial Words
• Combinatorial Queries and Updates on Partial Words
• An O(n log n) algorithm for finding all repetitions in a string
• Hard Counting Problems for Partial Words
• A note on the number of squares in a partial word with one hole
• Algorithms on Strings, Trees and Sequences
• On the number of squares in partial words
• Minimal Suffix and Rotation of a Substring in Optimal Time
• Efficient enumeration of non-equivalent squares in partial words with few holes