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 -