TY - GEN

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 - Waleń, Tomasz

PY - 2017/1/1

Y1 - 2017/1/1

N2 - A word of the form WW for some word (formula presented) is called a square, where \varSigma is an alphabet. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol which matches (agrees with) any symbol from. 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) the number of non-equivalent p-squares which are factors of a partial word T. Let (formula presented) be the maximum value of psquares (T) over all partial words of length n with at most k holes. We show asymptotically tight bounds: (formula presented) for some constants c:1,c_2>0. We also present an algorithm that computes psquares (T)(formula presented) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for (formula presented) 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 (formula presented) is called a square, where \varSigma is an alphabet. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol which matches (agrees with) any symbol from. 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) the number of non-equivalent p-squares which are factors of a partial word T. Let (formula presented) be the maximum value of psquares (T) over all partial words of length n with at most k holes. We show asymptotically tight bounds: (formula presented) for some constants c:1,c_2>0. We also present an algorithm that computes psquares (T)(formula presented) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for (formula presented) and its time complexity near-matches the maximum number of non-equivalent p-square factors in a partial word.

UR - http://www.scopus.com/inward/record.url?scp=85028448877&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028448877&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85028448877

SN - 9783319623887

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 99

EP - 111

BT - Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings

A2 - Cao, Yixin

A2 - Chen, Jianer

PB - Springer Verlag

T2 - 23rd International Conference on Computing and Combinatorics, COCOON 2017

Y2 - 3 August 2017 through 5 August 2017

ER -