特殊字符串的最大长度

056254628

由4种字符组成的一个字符串，若在它上面任意截取的长度为4的子字符串都不相同，那么这个字符串就称为特殊字符串。求特殊字符串的最大长度 。 －－－－－－－－－－－－－－－－－－－－－－－－－－ 比如 字符串 abcdbcda ， 能截取的子字符串有 abcd bcdb cdbc dbcd bcda ,它们互不相同，所以abcdbcda 是特殊字符串。 而 bbaaaaab , 能截取的子字符串有 bbaa baaa aaaa aaaa aaab ,其中第三个和第四个子字符串相同，所以 bbaaaaab 不是特殊字符串。

056254628

希望能给出一个最长特殊字符串的例子。

〇〇

4个字符的全排列有4！=24种 4N个字符的4字符子串有(4-1)N+1种

wiley

楼上, 字符是可以重复的, 所以有4^4=256种子字符串. 题目可以转化成寻找256个顶点的有向图(每个顶点4进4出, 除了aaaa, bbbb,cccc,dddd是3进3出)的哈密顿路径.

mathe

可以构造一个长度为256的M序列

〇〇

newkid又解出来了 1111211221222211131133133331114114414444112312322323323213212123332223312131312231323112412422424424214 2124442224412141412241424113221332113413433434434314313444333441314133414341234234324323442114221442324 23342433142314431143324132443214322431243421342234111

056254628

由n种字符组成的一个字符串，若在它上面任意截取的长度为m的子字符串都不相同，那么这个字符串就称为n*m型的特殊字符串。 那么能不能证明：n*m型的特殊字符串的最大长度为n^m+m-1。 对于每个特定的n、m，尽管都能用电脑来构造出一个最长的序列，但不算证明，因为这样的n、m有无穷个，例举不完的。 出这道题的目的就是：有时候仅仅依靠电脑是解决不了问题的，还是需要用人脑来解决，尤其是证明题（变量的取值有无数种的证明题）

mathe

当n为素数或素数的幂,利用m序列可以轻松构造结果

mathe

如果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)。