从大字典匹配子字符串的最快方法

Question

我有一些（通常 < 300 个符号长度）字符串，如“aabbccdcabcbbacdaaa”。

有python字典，其中键是类似格式的字符串，例如'bcccd'，键长度从10到100个符号不等。这本词典有一百万项。

我需要将我的初始字符串与字典的值相匹配，或者发现字典中没有正确的值。匹配条件：字典键应该在字符串内的某个地方（严格匹配）。

就计算速度而言，最好的方法是什么？我觉得应该有一些棘手的方法来散列我的初始字符串和字典键，以便应用一些聪明的子字符串搜索方法（如 Rabin-Karp 或 Knuth-Morris-Pratt）。或者后缀树状结构可能是一个很好的解决方案？

Answer 1

刚刚为 Python 找到了 Aho-Corasick 的合理实现 - pyahocorasick。从页面末尾的示例中获取：

import ahocorasick
A = ahocorasick.Automaton()

for k, v in your_big_dict.iteritems():
    A.add_word(k, v)

A.make_automaton()
for item in A.iter(your_long_string):
    print(item)