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

    直接用遍历就可以了吧?

    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为3,4,5时都没问题, 但是6就很慢,还有优化的空间
    暂时没有证明问题2,但看起来是成立的

       

      相似问题
      推荐文章