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 Walen

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

1 Citation (Scopus)
114 Downloads (Pure)


A word of the form WW for some word W∈Σ∗W∈Σ∗ is called a square, where ΣΣ is an alphabet. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol Open image in new window which matches (agrees with) any symbol from Open image in new window. 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. We denote by psquares(T)psquares(T) the number of non-equivalent p-squares which are factors of a partial word T. Let PSQUARESk(n)PSQUARESk(n) be the maximum value of psquares(T)psquares(T) over all partial words of length n with at most k holes. We show asymptotically tight bounds:c1⋅min(nk2,n2)≤PSQUARESk(n)≤c2⋅min(nk2,n2)c1⋅min(nk2,n2)≤PSQUARESk(n)≤c2⋅min(nk2,n2)for some constants c1,c2>0c1,c2>0 . We also present an algorithm that computes psquares(T)psquares(T) in O(nk3)O(nk3) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for k=O(1)k=O(1) and its time complexity near-matches the maximum number of non-equivalent p-square factors in a partial word.
Original languageEnglish
Title of host publicationComputing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings
EditorsYixin Cao, Jianer Chen
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Number of pages13
ISBN (Electronic)978-3-319-62389-4
ISBN (Print)978-3-319-62388-7
Publication statusE-pub ahead of print - 1 Jul 2017

Cite this