Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes

Panagiotis Charalampopoulos , Maxime Crochemore (1) , Costas Iliopoulos (2) , Tomasz Kociumaka (3) , Solon P Pissis (4) , Jakub Radoszewski (3) , Wojciech Rytter (3) , Tomasz Waleń

1 Informatics
2 DCS - Department of Computer Science
3 Institute of Informatics [Warsaw]
4 Department of Informatics [King's College London]

A partial word is a word with holes (also called don't cares: special symbols which match any symbol). A p-square is a partial word matching at least one standard square without holes (called a full square). Two p-squares are called equivalent if they match the same sets of full squares. Denote by psquares(T) the number of non-equivalent p-squares which are subwords of a partial word T. Let PSQUARES k (n) be the maximum value of psquares(T) over all partial words of length n with k holes. We show asympthotically tight bounds: c1 · min(nk 2 , n 2) ≤ PSQUARES k (n) ≤ c2 · min(nk 2 , n 2) for some constants c1, c2 > 0. We also present an algorithm that computes psquares(T) in O(nk 3) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for k = O(1) and its time complexity near-matches the maximum number of non-equivalent p-squares.

Domaines: Algorithme et structure de données [cs.DS]

Panagiotis Charalampopoulos, Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Solon P Pissis, et al.. Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes. COCOON, Aug 2017, Hong Kong, China. ⟨hal-01787563⟩