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

Question

要求找出长度为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时的解的数量的平方。但是能否证明？十分感谢诸大神。

Answer 1

关于计算字符串的问题，用了个比较笨的办法，思路：
1、将字符串形成一个有向图，这个图是有环的，图论算法掌握的不是太好啊，有谁有这方面研究的请指导；
2、然后选择某个节点做起点，求取可以遍历不重复节点的全部路径
3、按照节点顺序组合成字符串，如果字符串长度符合长度要求，则加回到结果集中，否则丢弃
4、计算结果集的空间大小，则得出全部结果数量，如果只要一条路径，在求得一个结果集的时候跳出就可以了
下面是用Python做的代码，有兴趣的可以一起研究算法优化的办法。
importsys
importtypes
deffind_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),res
deffind_sub(s_map,used,res,slen):
if(set(used)!=set(s_map)):
forxins_map[used[-1]]:
if(xnotinused):
used.append(x)
printused
if(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):
prints
res.add(s)
else:
find_sub(s_map,used,res,slen)
used.remove(x)
else:
continue
returnres
defbuild_map(s_list):
s_map=dict()
forsins_list:
l=(s_list[0:])
l.remove(s)
s_map[s]=[iforiinlifs[1:]==i[:-1]]
returns_map
defbinary_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()))
                            

Answer 2

直接用遍历就可以了吧？
importsys
#listallbitstringwithalength2^k+k-1,and
#eachksubstringisdifferent
classbitString:
def__init__(self,k):
self.k=k
self.num=0
defgenerate(self):
self.num+=1
defgetString(self):
s=bin(self.num)[2:]
return"0"*(self.k-len(s))+s
deftryAppend(bitStr,k,oneBit,stringSet):
#print"tring:",bitStr,":",oneBit
newString=bitStr[-(k-1):]+oneBit
ifint(newString,2)instringSet:
return
eliflen(bitStr)==2**k+k-2:
print"found:",bitStr+oneBit
return
stringSet.add(int(newString,2))
#printstringSet
tryAppend(bitStr+oneBit,k,"0",stringSet)
tryAppend(bitStr+oneBit,k,"1",stringSet)
stringSet.discard(int(newString,2))
defgeneratBitString(initString,k):
s=set()
s.add(int(initString,2))
#prints
tryAppend(initString,k,"0",s)
tryAppend(initString,k,"1",s)
defgeneratBitStringAll(k):
b=bitString(k)
foriinrange(2**k):
generatBitString(b.getString(),k)
b.generate()
pass
if__name__=="__main__":
k=int(sys.argv[1])
generatBitStringAll(k)
要生成全部，就调用generatBitStringAll，只要生成部分，就只需要调用generatBitStrings
测试了一下，计算k为３，４，５时都没问题，　但是６就很慢，还有优化的空间
暂时没有证明问题２，但看起来是成立的