包含每一个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

搜索大量字符串的一种非常快速的方法是使用一个有限自动机（因此您对regexp的猜测还不算太远），即Aho Corasick string matching机器，它用于grep，病毒扫描程序等工具中。在

首先，它将要搜索的字符串（在您的例子中是A中的单词）编译成一个具有失败函数的有限状态自动机（如果您对细节感兴趣，请参阅'75年的paper）。然后，这个自动机读取输入字符串并输出所有找到的搜索字符串（您可能需要对其进行一点修改，以便它也输出在其中找到搜索字符串的字符串）。在

这种方法的优点是可以同时搜索所有的搜索字符串，因此只需查看输入字符串的每个字符一次（线性复杂度）！在

有implementations of the aho corasick pattern matcher at pypi，但我还没有测试过它们，所以我不能说这些实现的性能、可用性或正确性。在

---

编辑：我尝试了Aho-Corasick自动机的this实现，它确实是目前建议的方法中速度最快的，而且也很容易使用：

import pyahocorasick

def aho(A, B):
    t = pyahocorasick.Trie();
    for a in A:
        t.add_word(a, a)
    t.make_automaton()
    return [(s,b) for b in B for (i,res) in t.iter(b) for s in res]

不过，我观察到的一件事是，当用@SvenMarnachs脚本测试这个实现时，它产生的结果比其他方法稍少一些，我不知道为什么。我给创造者写了封信，也许他会想出来的。在

Answer 2

假设你的单词有一个合理的大小（比如10个字母）。执行以下操作以实现线性（！）时间复杂性，即O(A+B)：

• 初始化哈希表或trie
• 对于b中的每个字符串b：
  • 对于该字符串的每个子字符串
    • 将子字符串添加到hashtable/trie（这不比55*O(B)=O(B)）更糟糕），并使用它所属的字符串的元数据
• 对于a中的每个字符串a：
  • 对hashtable/trie执行一个O(1)查询以查找它所在的所有B字符串，生成这些字符串

（在写下这个答案时，如果OP的“单词”是有界的，还没有反应。如果它们是无界的，这个解决方案仍然适用，但是有一个O(maxwordsize^2)的依赖关系，尽管实际上它在实践中更好，因为并非所有单词的大小都相同，所以它可能与分布正确的O(averagewordsize^2)一样好。例如，如果所有单词的大小都是20，那么问题大小将比大小为10的情况下增加4倍。但是，如果从10到20的大小增加足够少的单词，那么复杂性不会有太大变化。）

编辑：https://stackoverflow.com/q/8289199/711085实际上是一个理论上更好的答案。在这个答案发布之前，我正在查看维基百科的链接页面，当时我在想“字符串大小的线性不是你想要的”，后来才意识到这正是你想要的。您构建regexp(Aword1|Aword2|Aword3|...)的直觉是正确的，因为在幕后生成的有限自动机如果支持同时重叠匹配，那么它将快速执行匹配，而不是所有regexp引擎都可能这样做。最终，您应该使用什么取决于您是否计划重用As或Bs，或者这只是一次性的事情。上面的技术更容易实现，但只有在单词有界的情况下才有效（如果不拒绝超过一定大小限制的单词，则会引入DoS漏洞），但如果您不希望使用Aho-Corasick string matching finite automaton或类似内容，或者它不能作为库使用，则可能是您要寻找的。在

Answer 3

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

[(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:使用集合而不是列表来消除重复项。（我没有更新时间——它们基本上保持不变。）