|
1. 引言 设是一个有限非空集, 称为字母表; 中的元素称为字母; 上的有限序列称为字. 其中空序列叫做空字,记为1. http://www.paper51.com 设是上的字, 其中,,则中所含字母的个数称为的长度,记为,令表示中出现的字母组成的集合, http://www.paper51.com 设和是上的两个字,其中,, , 定义字的联接运算如下: 内容来自论文无忧网 www.paper51.com ,,, . paper51.com 令是上的字. 称为的前缀, 若存在上的字, 使得. 相应地可定义后缀的概念. paper51.com
我们有时也会用到无限字的概念, 通常称上的无限序列 内容来自论文无忧网 www.paper51.com , , 内容来自www.paper51.com
为无限字. 相对于无限字的概念, 前面定义的字也称有限字. copyright paper51.com 设为上的有限字, 其中, . 则记 内容来自www.paper51.com . http://www.paper51.com
显然为上的一个无限字, 称为由生成的无限字. paper51.com 设为有限字, 为无限字, , , . 则定义与的连接为运算为 内容来自www.paper51.com . paper51.com
显然为无限字. 内容来自www.paper51.com 称有限字为无限字的前缀, 若存在无限字使得. 这时, 也称为 copyright paper51.com 的后缀. 内容来自www.paper51.com 注意: 有限字可以连接有限字, 也可连接无限字, 但无限字不能连接任何字. 另外, 无限字的前缀一定是有限字, 后缀一定是无限字. 内容来自www.paper51.com 设与为两个自然数, 我们用表示与的最大公约数. http://www.paper51.com
定理1 (Fine-Wilf 定理, 见[1]). 设和是上的两个字, 长度分别为和, . 若存在自然数与使得与有长度至少为的公共前缀, 则与是同一个长度为1的字(即字母)的幂. paper51.com Fine-Wilf定理在研究字方程、字的周期性以及字序列分析等方面有着重要的应用, 是字的组合学中一个重要的定理. 此定理表现的意思是当两个字和的若干次幂有充分长 (上述定理中的) 的公共前缀时, 和将有很强的制约关系 (即它们是同一个字的幂). 那么, 我们要问: 如果上述公共前缀的长度没有那么长, 还能保证和有如此关系吗? copyright paper51.com
结论是否定的. Fine-Wilf定理已经做到了最好, 不可能再改进了. 即上述公共前缀的界限哪怕只是减小为, 都不能得出和是同一个字的幂. 我们将在第2节中讨论这样的例子. copyright paper51.com 一般来说, 和的公共前缀越短, 它们之间的联系就越弱. 我们将在第3节中讨论和的若干次幂有长度为的公共前缀时, 和的关系, 其中为自然数. 这一关系 (即第3节的主要结果) 可以看作Fine-Wilf 定理的推广. 内容来自论文无忧网 www.paper51.com 注: 定理1中只讨论了和的长度互素的情形, 一般情形的Fine-Wilf定理如下: http://www.paper51.com
设和是上的两个字, 长度分别为和, . 若存在自然数与使得与有长度至少为的公共前缀, 则与是同一个长度为的字的幂. http://www.paper51.com 由于Fine-Wilf定理的这个一般情形的证明可由定理1简单的推出 (证明参见[1]或[2]), 为简单起见, 本文只讨论与互素的情况. 内容来自论文无忧网 www.paper51.com 本文未定义的符号和术语都是标准的, 可参见文[2]或[3]. paper51.com v[i%=max]=ch;//给 v 的指定位赋值. 内容来自论文无忧网 www.paper51.com
} copyright paper51.com for(i=0;i<min; i++) //利用 v 生成前缀 u. 内容来自论文无忧网 www.paper51.com
u[i]=v[i]; paper51.com printf("u= %s\nv = %s\n",u,v); //输出字 u 和 v. paper51.com } paper51.com |