How Many Squares Can a String Contain?

✍ Scribed by Aviezri S. Fraenkel; Jamie Simpson

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 241 KB
• Volume: 82
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2843

✦ Synopsis

All our words (strings) are over a fixed alphabet. A square is a subword of the form uu=u 2 , where u is a nonempty word. Two squares are distinct if they are of different shape, not just translates of each other. A word u is primitive if u cannot be written in the form u=v j for some j 2. A square u 2 with u primitive is primitive rooted. Let M(n) denote the maximum number of distinct squares, P(n) the maximum number of distinct primitive rooted squares in a word of length n. We prove: no position in any word can be the beginning of the rightmost occurrence of more than two squares, from which we deduce M(n)<2n for all n>0, and P(n)=n&o(n) for infinitely many n.