Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Monday, May 7, 2018 - 4:16:45 PM
Last modification on : Saturday, June 25, 2022 - 11:09:00 AM
Long-term archiving on: : Monday, September 24, 2018 - 7:35:19 PM


Files produced by the author(s)


  • HAL Id : hal-01787563, version 1



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⟩



Record views


Files downloads