On the number of squares in partial words
Vesa Halava, Tero Harju, Tomi Kärki (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word of length can contain is less than . This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is , where is the size of the alphabet. Moreover, we prove that the number of distinct squares in...