特殊字符串的最大长度

056254628

本题跟格雷码还是不同的，它要求相邻的两个组合，是xS、Sy之型，S是长度为m－1的串。

mathe

由n种字符组成的一个字符串，若在它上面任意截取的长度为m的子字符串都不相同，那么这个字符串就称为n*m型的特殊字符串。
那么能不能证明：n*m型的特殊字符串的最大长度为n^m+m-1。
对于每个特定的n、m，尽管都能用 ...
056254628 发表于 2009-10-7 13:55

这个推广问题可以通过图论来解决.
我们的目的还是找一个长度位$n^m$的环,环上任意连续m个字符构成的子串都不相同.
为此,我们可以构造一个含有$n^{m-1}$个点的图,其中每个点用一个长度为m-1的字符串来标识(不同的点有不同的字符串标识).
如果点A的字符串标识的最后m-2个字母同点B的字符串标识的前面m-2个字母相同(包含顺序相同),那么我们做一条从A到B的有向边.
于是这个图上,从每个点都正好发出n条边,而且也进入n条边,而且显然图连通.
于是欧拉回路存在.我们选择一条欧拉回路,将这个欧拉回路上所有点的字符串标识的第一个字母连接起来,就是一个解.

056254628

我看到一个用数学归纳法来证明的：
  从一个给定的特殊字符串(一个序列)，可以按照以下构造方法，让它不断增长，直到达到最长长度。
n* m一般情况。
第一步：在序列中检查末尾m-1个字符构成的字符串，若除末尾外，最多找到n-1处，那么肯定能在末尾加上一个字符，使得它是特殊字符串。
第二步：若找到n次，那么，其头m-1个字符与尾m-1个字符必定相等，将尾部这m-1个字符剪掉，使头尾相接成为环。
第三步：在环中找只出现n-1次或以下次的长度为m-1的字符串，找到，在其尾部剪断，在头部加上该字符串，得到新序列，其与原序列等长，那么肯定能在其末尾加上一个字符，使得它是特殊字符串。
--------------------------------------
如果上述三步都无法进行，那么该特殊字符串已达到最大长度n^m+m-1。

〇〇

格雷码可以通过自然2进制数构造，这个也就相当于n进制...