## 早起的鸟儿有虫吃 查看完整档案

|    |
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

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

``````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

#print stringSet
tryAppend(bitStr+oneBit, k, "0", stringSet)
tryAppend(bitStr+oneBit, k, "1", stringSet)

def generatBitString(initString, k):
s = set()
#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)
``````