• 4.3k

长度为 2^k + k - 1 的 binary string,使其任意一个长度为 k 的 substring 都是唯一的

要求找出长度为 2^k + k -1 的 binary string,其任意一个长度为 k 的 substring 都是唯一的。

例如,当 k = 2 时,需要找到长度为 5 的 binary string,使其任意连续两位在整个 string 内是唯一的。满足条件的解共有 4 个:
00110100111100101100。以 00110 为例,00011110 都只出现了一次。

k = 3 时,就需要找到长度为 10 的 binary string,使其任意连续三位在整个 string 内是唯一的。一共有 16 个解,其中字典序最小一个是 0001011100
k = 4 时,有 256 个解,其中字典序最小的一个是 0000100110101111000
k = 5 时,有 65536 个解,其中一个是 000001000110010100111010110111110000

现在我想问的两个问题是:
1、有什么算法可以快速找出一个任意解,或是找出所有的解?
2、看起来似乎 k = n 时的解的数量是 k = n-1 时的解的数量的平方。但是能否证明?

十分感谢诸大神。

阅读 3.8k
评论
    4 个回答

    2^k + k -1长度的串,共有2^k个substring。长度为k的string也就是2^k个,所以每个string都要出现有且仅有一次。

    假设串的k-1前缀是s,串就是sx。我们有如下的顺序满足。sx->ys!x->!ys,其中!x表示x取反,!y同理。->表示中间可能存在其它字符(不能有包含s前缀或者后缀的子串)。

    待续。。。

      相似问题
      推荐文章