相关疑难解决方法(0)

我有两套串(中A和B),我想知道的所有字符串对a in A,并b in B在那里a是一个子b.

对此进行编码的第一步如下:

for a in A:
    for b in B:
        if a in b:
            print (a,b)

但是,我想知道 - 使用正则表达式是否有更有效的方法(例如,而不是检查if a in b:,检查正则表达式是否'.*' + a + '.*':匹配'b'.我认为可能使用这样的东西会让我缓存Knuth-莫里斯-普拉特对所有故障的功能a.此外,使用列表理解为内for b in B:循环可能会给出一个相当大的加速(和嵌套列表理解可能会更好).

我对这个算法的渐近运行时间的巨大飞跃并不感兴趣(例如使用后缀树或其他复杂而聪明的东西).我更关心常量(我只需要为几对A和B集合做这个,我不希望它一整周都运行).

您是否知道任何技巧或有任何通用建议来更快地完成此操作？非常感谢您分享的任何见解!

编辑:

使用@ninjagecko和@Sven Marnach的建议,我构建了一个10-mer的快速前缀表:

    import collections
    prefix_table = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i in xrange(len(prot_seq)-10):
            j …