How many squares can a string contain?
How many squares can a string contain?
复制标题
DOI：
10.1006/jcta.1997.2843
复制
发表时间：
1998-04-01
影响因子：
1.1
通讯作者：
Simpson, J
中科院分区：
文献类型：
--
作者：
Fraenkel, AS;Simpson, J
我们所有的单词（字符串）都是在一个发射字母表上。一个正方形是一个子字的形式uu = u（2），其中u是一个非空字。如果两个正方形的形状不同，那么它们是不同的，而不仅仅是彼此的平移。一个词u是本原的，如果u不能写成u = v（j）的形式，其中j大于或等于2。设M（n）表示长度为1的字中不同平方数的最大值，P（n）表示长度为1的字中不同本原根平方数的最大值.我们证明：在任何字的位置可以是开始的最右边出现的两个以上的广场，从中我们推出M（n）< 2n for all n >0，和P（n）= n-o（n）的无限多个n。(C)北京：科学出版社.
All our words (strings) are over a fired 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 greater than or equal to 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,1. 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. (C) 1998 Academic Press.