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

TY - CHAP

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

AU - Charalampopoulos, Panagiotis

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Kociumaka, Tomasz

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Walen, Tomasz

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-62389-4_9

DO - 10.1007/978-3-319-62389-4_9

M3 - Chapter

SN - 978-3-319-62388-7

VL - 10392

SP - 99

EP - 111

BT - Computing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings

A2 - Cao, Yixin

A2 - Chen, Jianer

PB - Springer International Publishing Switzerland

CY - Cham

ER -