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

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

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

A word of the form WW for some word W∈ Σ is called a square. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol ◊∉ Σ which matches any symbol from Σ∪ { ◊}. A p-square is a partial word matching at least one square WW without holes. Two p-squares are called equivalent if they match the same set of squares. A p-square is called here unambiguous if it matches exactly one square WW without holes. Such p-squares are natural counterparts of classical squares. Let PSQUARES k (n) and USQUARES k (n) be the maximum number of non-equivalent p-squares and non-equivalent unambiguous p-squares in T over all partial words T of length n with at most k holes. We show asymptotically tight bounds: PSQUARESk(n)=Θ(min(nk2,n2)),USQUARESk(n)=Θ(nk).We present an algorithm that reports all non-equivalent p-squares in O(nk 3 ) time for a partial word of length n with k holes, for an integer alphabet. In particular, it runs in linear time for k= O(1) and its time complexity near-matches the asymptotic bound for PSQUARES k (n). We also show an O(n) -time algorithm that reports all non-equivalent p-squares of a given length. The paper is a full and improved version of Charalampopoulos et al. (in Cao Y, Chen Y (eds) Proceedings of the 23rd international conference on computing and combinatorics, COCOON 2017; Springer, 2017).

Original languageEnglish
Pages (from-to)501-522
Number of pages22
JournalJournal of Combinatorial Optimization
Volume37
Issue number2
DOIs
Publication statusPublished - 15 Feb 2019
Externally publishedYes

Keywords

  • Approximate period
  • Lyndon word
  • Partial word
  • Square in a word

Fingerprint

Dive into the research topics of 'Efficient enumeration of non-equivalent squares in partial words with few holes'. Together they form a unique fingerprint.

Cite this