包含每一个oth的有效字符串

Question

我有两组字符串（A和B），我想知道所有字符串对a in A和{}，其中a是{}的子字符串。在

编码的第一步是：

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

但是，我想知道——有没有一种更有效的方法来处理正则表达式（例如，不是检查if a in b:，而是检查regexp'.*' + a + '.*':是否与'b'匹配。我想也许使用这样的方法可以让我为所有a缓存Knuth-Morris-Pratt失败函数。此外，对内部for b in B:循环使用列表理解可能会带来相当大的加速（嵌套列表理解可能会更好）。在

我对在算法的渐进运行时实现一个巨大的飞跃不是很感兴趣（例如使用后缀树或任何其他复杂和聪明的东西）。我更关心常量（我只需要对几对A和B集执行此操作，我不希望它运行一周）。在

你知道什么诀窍或者有什么通用的建议来更快地完成这个任务吗？非常感谢您的任何见解！在

---

编辑：

根据@ninjagecko和@Sven Marnach的建议，我构建了一个包含10个mer的快速前缀表：

^{pr2}$

Answer 1

当然，您可以很容易地将以下内容写成列表理解：

[(a, b) for a in A for b in B if a in b]

这可能会稍微加快循环速度，但不要期望太高。我怀疑使用正则表达式对这个问题有任何帮助。在

编辑：以下是一些计时：

^{pr2}$

结果：

Nested loop [0.3641810417175293, 0.36279606819152832, 0.36295199394226074]
List comprehension [0.362030029296875, 0.36148500442504883, 0.36158299446105957]
Regular expressions [1.6498990058898926, 1.6494300365447998, 1.6480278968811035]
ninjagecko [0.06402897834777832, 0.063711881637573242, 0.06389307975769043]

编辑2:在计时中添加了alogrithm suggested by ninjagecko的变体。你可以看到它比所有的暴力手段都要好得多。在

编辑3:使用集合而不是列表来消除重复项。（我没有更新时间——它们基本上保持不变。）