<p>搜索大量字符串的一种非常快速的方法是使用一个<strong>有限自动机</strong>(因此您对regexp的猜测还不算太远),即<a href="http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm" rel="nofollow">Aho Corasick string matching</a>机器,它用于<em>grep</em>,<em>病毒扫描程序</em>等工具中。在</p>
<p>首先,它将要搜索的字符串(在您的例子中是A中的单词)编译成一个具有失败函数的有限状态自动机(如果您对细节感兴趣,请参阅'75年的<a href="http://www.google.se/url?sa=t&rct=j&q=aho%20corasick%20pdf&source=web&cd=1&ved=0CBoQFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.4671&rep=rep1&type=pdf&ei=yKjSTpOVGan-4QSkpqRg&usg=AFQjCNHVgQ6sWmDUsawqw61MCu_16__iog" rel="nofollow">paper</a>)。然后,这个自动机读取输入字符串并输出所有找到的搜索字符串(您可能需要对其进行一点修改,以便它也输出在其中找到搜索字符串的字符串)。在</p>
<p>这种方法的优点是可以同时搜索所有的搜索字符串,因此只需查看输入字符串的每个字符一次(<em>线性复杂度</em>)!在</p>
<p>有<a href="http://pypi.python.org/pypi?%3aaction=search&term=ahocorasick&submit=search" rel="nofollow">implementations of the aho corasick pattern matcher at pypi</a>,但我还没有测试过它们,所以我不能说这些实现的性能、可用性或正确性。在</p>
<hr/>
<p><strong>编辑</strong>:我尝试了Aho-Corasick自动机的<a href="http://pypi.python.org/pypi/pyahocorasick/1.0" rel="nofollow">this</a>实现,它确实是目前建议的方法中速度最快的,而且也很容易使用:</p>
<pre><code>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]
</code></pre>
<p>不过,我观察到的一件事是,当用@SvenMarnachs脚本测试这个实现时,它产生的结果比其他方法稍少一些,我不知道为什么。我给创造者写了封信,也许他会想出来的。在</p>