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 metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01787563
Contributor : Maxime Crochemore <>
Submitted on : Monday, May 7, 2018 - 4:16:45 PM
Last modification on : Friday, June 1, 2018 - 2:34:04 PM
Long-term archiving on : Monday, September 24, 2018 - 7:35:19 PM

File

squares_partial.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01787563, version 1

Collections

Citation

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

Share

Metrics

Record views

56

Files downloads

138