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

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

例如，当k=2时，需要找到长度为5的binarystring，使其任意连续两位在整个string内是唯一的。满足条件的解共有4个：00110、10011、11001、01100。以00110为例，00、01、11、10都只出现了一次。k=3时，就需要找到长度为10的binarystring，使其任意连续三位在整个string内是唯一的。一共有16个解，其中字典序最小一个是0001011100。k=4时，有256个解，其中字典序最小的一个是0000100110101111000。k=5时，有65536个解，其中一个是000001000110010100111010110111110000。现在我想问的两个问题是：1、有什么算法可以快速找出一个任意解，或是找出所有的解？2、看起来似乎k=n时的解的数量是k=n-1时的解的数量的平方。但是能否证明？十分感谢诸大神。

关于计算字符串的问题，用了个比较笨的办法，思路：1、将字符串形成一个有向图，这个图是有环的，图论算法掌握的不是太好啊，有谁有这方面研究的请指导；2、然后选择某个节点做起点，求取可以遍历不重复节点的全部路径3、按照节点顺序组合成字符串，如果字符串长度符合长度要求，则加回到结果集中，否则丢弃4、计算结果集的空间大小，则得出全部结果数量，如果只要一条路径，在求得一个结果集的时候跳出就可以了下面是用Python做的代码，有兴趣的可以一起研究算法优化的办法。importsysimporttypesdeffind_path(s_map,slen):res=set()if(s_map):foriins_map:used=list()used.append(i)res=find_sub(s_map,used,res,slen)returnlen(res),resdeffind_sub(s_map,used,res,slen):if(set(used)!=set(s_map)):forxins_map[used[-1]]:if(xnotinused):used.append(x)printusedif(set(used)==set(s_map)):sub=used[:-1]s=''foriinsub:s+=i[0]s+=used[-1]prints,len(s),len(s_map)if(len(s)==slen):printsres.add(s)else:find_sub(s_map,used,res,slen)used.remove(x)else:continuereturnresdefbuild_map(s_list):s_map=dict()forsins_list:l=(s_list[0:])l.remove(s)s_map[s]=[iforiinlifs[1:]==i[:-1]]returns_mapdefbinary_strings(k):iftype(k)istypes.IntType:return[(str(bin(i))[2:]).rjust(k,'0')foriinxrange(2**k)]defmain():printfind_path(build_map(binary_strings(2)),2**2+2-1)printfind_path(build_map(binary_strings(3)),2**3+3-1)printfind_path(build_map(binary_strings(4)),2**4+4-1)if__name__=='__main__':sys(exit(main()))

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

2回答