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

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

    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()))
    

      直接用遍历就可以了吧?

      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,但看起来是成立的

         

        • 13.2k

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

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

          2^k + k -1长度的串,共有2^k个substring。长度为k的string也就是2^k个,所以每个string都要出现有且仅有一次。

          假设串的k-1前缀是s,串就是sx。我们有如下的顺序满足。sx->ys!x->!ys,其中!x表示x取反,!y同理。->表示中间可能存在其它字符(不能有包含s前缀或者后缀的子串)。

          待续。。。

            撰写回答

            登录后参与交流、获取后续更新提醒

            相似问题
            推荐文章