ON THE NUMBER OF SQUARES IN PARTIAL WORDS

The theorem of Fraenkel and Simpson states that the maximumnumber of distinct squares that a word w of length n can containis less than 2n. This is based on the fact that no more than two squarescan have their last occurrences starting at the same position. In thispaper we show that the maximum number of the last occurrences ofsquares per position in a partial word containing one hole is 2k, wherek is the size of the alphabet. Moreover, we prove that the numberof distinct squares in a partial word with one hole and of length n isless than 4n, regardless of the size of the alphabet. For binary partialwords, this upper bound can be reduced to 3n