Efficient enumeration of non-equivalent squares in partial words with few holes
From MaRDI portal
Publication:5971176
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
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
