Efficient enumeration of non-equivalent squares in partial words with few holes (Q5971176)
From MaRDI portal
scientific article; zbMATH DE number 7063559
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient enumeration of non-equivalent squares in partial words with few holes |
scientific article; zbMATH DE number 7063559 |
Statements
Efficient enumeration of non-equivalent squares in partial words with few holes (English)
0 references
6 June 2019
0 references
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.
0 references
partial word
0 references
square in a word
0 references
square factor
0 references
hole
0 references
Lyndon root
0 references
Lyndon word
0 references
approximate period
0 references