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

A word of the form WW for some word $$W\in \varSigma ^*$$ W ∈ Σ ∗ is called a square. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol $$\lozenge \notin \varSigma $$ ◊ ∉ Σ which matches any symbol from $$\varSigma \cup \{\lozenge \}$$ Σ ∪ { ◊ } . 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. A p-square is called here unambiguous if it matches exactly one square WW without holes. Such p-squares are natural counterparts of classical squares. Let $$\mathrm {PSQUARES}_k(n)$$ PSQUARES k ( n ) and $$\mathrm {USQUARES}_k(n)$$ USQUARES k ( n ) be the maximum number of non-equivalent p-squares and non-equivalent unambiguous p-squares in T over all partial words T of length n with at most k holes. We show asymptotically tight bounds: $$\begin{aligned} \mathrm {PSQUARES}_k(n) = \varTheta (\min (nk^2,\, n^2)),\ \ \mathrm {USQUARES}_k(n) = \varTheta (nk). \end{aligned}$$ PSQUARES k ( n ) = Θ ( min ( n k 2 , n 2 ) ) , USQUARES k ( n ) = Θ ( n k ) . We present an algorithm that reports all non-equivalent p-squares in $$\mathcal {O}(nk^3)$$ O ( n k 3 ) time for a partial word of length n with k holes, for an integer alphabet. In particular, it runs in linear time for $$k=\mathcal {O}(1)$$ k = O ( 1 ) and its time complexity near-matches the asymptotic bound for $$\mathrm {PSQUARES}_k(n)$$ PSQUARES k ( n ) . We also show an $$\mathcal {O}(n)$$ O ( n ) -time algorithm that reports all non-equivalent p-squares of a given length. The paper is a full and improved version of Charalampopoulos et al. (in Cao Y, Chen Y (eds) Proceedings of the 23rd international conference on computing and combinatorics, COCOON 2017; Springer, 2017).