Efficient enumeration of non-equivalent squares in partial words with few holes

Autor: Wojciech Rytter, Maxime Crochemore, Tomasz Kociumaka, Tomasz Waleń, Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Costas S. Iliopoulos
Rok vydání: 2018
Předmět:
Zdroj: Journal of Combinatorial Optimization. 37:501-522
ISSN: 1573-2886
1382-6905
DOI: 10.1007/s10878-018-0300-z
Popis: A word of the form WW for some word \(W\in \varSigma ^*\) 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 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)\) the number of non-equivalent p-squares which are factors of a partial word T. Let \(\mathrm {PSQUARES}_k(n)\) be the maximum value of \( psquares (T)\) over all partial words of length n with at most k holes. We show asymptotically tight bounds: $$ c_1\cdot \min (nk^2,\, n^2) \le \mathrm {PSQUARES}_k(n) \le c_2\cdot \min (nk^2,\, n^2) $$ for some constants \(c_1,c_2>0\). We also present an algorithm that computes \( psquares (T)\) in \(\mathcal {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=\mathcal {O}(1)\) and its time complexity near-matches the maximum number of non-equivalent p-square factors in a partial word.
Databáze: OpenAIRE
Externí odkaz: