• 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()))
    
      相似问题
      推荐文章