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

Question

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

例如，当 k = 2 时，需要找到长度为 5 的 binary string，使其任意连续两位在整个 string 内是唯一的。满足条件的解共有 4 个：
00110、10011、11001、01100。以 00110 为例，00、01、11、10 都只出现了一次。

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

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

十分感谢诸大神。

Answer 1

关于计算字符串的问题，用了个比较笨的办法，思路：

1、将字符串形成一个有向图，这个图是有环的，图论算法掌握的不是太好啊，有谁有这方面研究的请指导；
2、然后选择某个节点做起点，求取可以遍历不重复节点的全部路径
3、按照节点顺序组合成字符串，如果字符串长度符合长度要求，则加回到结果集中，否则丢弃
4、计算结果集的空间大小，则得出全部结果数量，如果只要一条路径，在求得一个结果集的时候跳出就可以了

下面是用Python做的代码，有兴趣的可以一起研究算法优化的办法。

import sys
import types

def find_path(s_map, slen):
    res = set()
    if (s_map):
        for i in s_map:
            used = list()
            used.append(i)
            res = find_sub(s_map, used, res, slen)

    return len(res),res

def find_sub(s_map, used, res, slen):
    if (set(used) != set(s_map)):
        for x in s_map[used[-1]]:
            if (x not in used):
                used.append(x)
                print used

                if (set(used) == set(s_map)):
                    sub = used[:-1]
                    s = ''
                    for i in sub:
                        s += i[0]
                    s += used[-1]
                    print s, len(s), len(s_map)
                    if (len(s) == slen):
                        print s
                        res.add(s)
                else:
                    find_sub(s_map, used, res, slen)
                used.remove(x)
            else:
                continue

    return res

def build_map(s_list):
    s_map = dict()

    for s in s_list:
        l = (s_list[0:])
        l.remove(s)
        s_map[s] = [i for i in l if s[1:] == i[:-1]]

    return s_map        

def binary_strings(k):
    if type(k) is types.IntType:
        return [(str(bin(i))[2:]).rjust(k, '0') for i in xrange(2 ** k) ]

def main():
    print find_path(build_map(binary_strings(2)), 2**2+2-1)
    print find_path(build_map(binary_strings(3)), 2**3+3-1)
    print find_path(build_map(binary_strings(4)), 2**4+4-1)

if __name__ == '__main__':
    sys(exit(main()))

Answer 2

直接用遍历就可以了吧？

import sys

# list all bitstring with a length 2^k + k - 1, and
# each k substring is different

class bitString:
    def __init__(self, k):
        self.k = k
        self.num = 0
    def generate(self):
        self.num += 1
    def getString(self):
        s = bin(self.num)[2:]
        return "0"*(self.k - len(s)) + s

def tryAppend(bitStr, k, oneBit, stringSet):
    #print "tring: ", bitStr, " : ",  oneBit
    newString = bitStr[-(k-1):] + oneBit
    if int(newString,2) in stringSet:
        return
    elif len(bitStr) == 2**k + k - 2:
        print "found: ", bitStr+oneBit
        return

    stringSet.add(int(newString,2))
    #print stringSet
    tryAppend(bitStr+oneBit, k, "0", stringSet)
    tryAppend(bitStr+oneBit, k, "1", stringSet)
    stringSet.discard(int(newString,2))

def generatBitString(initString, k):
    s = set()
    s.add(int(initString, 2))
    #print s

    tryAppend(initString, k,  "0", s)
    tryAppend(initString, k,  "1", s)

def generatBitStringAll(k):
    b = bitString(k)
    for i in range(2**k):
        generatBitString(b.getString(), k)
        b.generate()
    pass

if __name__ == "__main__":
    k = int(sys.argv[1])
    generatBitStringAll(k)

要生成全部，就调用generatBitStringAll，只要生成部分，就只需要调用generatBitStrings
测试了一下，计算k为３，４，５时都没问题，　但是６就很慢，还有优化的空间
暂时没有证明问题２，但看起来是成立的

　　　

Answer 3

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

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

Answer 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前缀或者后缀的子串）。

待续。。。