• 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 个回答
    • 13.3k

    生成一个格雷码码表,其中任意连续 2^k <<即 (2^k + k - 1) - (k - 1)>> 个码字可以构成本命题的一个解。

    其他的自己发散思考吧……(以上内容理解有错)

      相似问题
      推荐文章