特殊字符串的最大长度
由4种字符组成的一个字符串，若在它上面任意截取的长度为4的子字符串都不相同，那么这个字符串就称为特殊字符串。求特殊字符串的最大长度 。－－－－－－－－－－－－－－－－－－－－－－－－－－
比如 字符串 abcdbcda， 能截取的子字符串有abcdbcdbcdbc dbcdbcda ,它们互不相同，所以abcdbcda 是特殊字符串。
而bbaaaaab ,能截取的子字符串有bbaa baaa aaaaaaaaaaab ,其中第三个和第四个子字符串相同，所以bbaaaaab 不是特殊字符串。 希望能给出一个最长特殊字符串的例子。 4个字符的全排列有4！=24种
4N个字符的4字符子串有(4-1)N+1种 本帖最后由 wiley 于 2009-10-7 01:44 编辑
楼上, 字符是可以重复的, 所以有4^4=256种子字符串.
题目可以转化成寻找256个顶点的有向图(每个顶点4进4出, 除了aaaa, bbbb,cccc,dddd是3进3出)的哈密顿路径. 可以构造一个长度为256的M序列 newkid又解出来了
1111211221222211131133133331114114414444112312322323323213212123332223312131312231323112412422424424214
2124442224412141412241424113221332113413433434434314313444333441314133414341234234324323442114221442324
23342433142314431143324132443214322431243421342234111 由n种字符组成的一个字符串，若在它上面任意截取的长度为m的子字符串都不相同，那么这个字符串就称为n*m型的特殊字符串。
那么能不能证明：n*m型的特殊字符串的最大长度为n^m+m-1。
对于每个特定的n、m，尽管都能用电脑来构造出一个最长的序列，但不算证明，因为这样的n、m有无穷个，例举不完的。
出这道题的目的就是：有时候仅仅依靠电脑是解决不了问题的，还是需要用人脑来解决，尤其是证明题（变量的取值有无数种的证明题） 当n为素数或素数的幂,利用m序列可以轻松构造结果 如果n是素数或素数的幂,$F_n$为n阶域.
任意选择$F_n$的m次一个本原多项式G(x),以及一个常系数为1的m-1次多项式C(x)
我们将${C(x)}/{G(x)}$展开成泰勒级数,那么多项式系数是一个周期为$n^m-1$的数列.
其中任意位置的连续m个数都互不相同,而且不存在连续m个0.
在一个周期中任意找一个含有m-1个连续0的位置,在其中添加一个0,得到一个长度为$n^m$的环,其中任意m个连续数都互不相同,正好取遍所有$n^m$种组合.
可以参考R10下的广义斐波那契序列 格雷码是一个长度为2^n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为2^3的格雷码为(000,001,011,010,110,111,101,100)。
页:
[1]
2