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

The paper investigates non-equivalent squares of partial words over a finite alphabet. The concept of equivalence of p-square factors in partial words is introduced and an \(O(nk^3)\)-time algorithm enumerating all non-equivalent p-square factors in a partial word of length \(n\) with \(k\) holes is developed. The authors also propose a linear-time algorithm that enumerates all non-equivalent p-squares of a fixed half length. Finally, asymptotically tight estimations of the numbers of non-equivalent p-squares and non-equivalent unambiguous p-squares are derived for a partial word with a limited number of holes.