我有 Aho-Corasick 算法的代码。但我仍然不明白在给定字符串列表中搜索文本时如何在查找过程中使用状态信息。
例如,我有一个字符串列表 [MOSCOW][COLA]
,现在我需要确定 CA
是否在列表中,如果是,则是什么它的位置?
这是一个link to the code .
最佳答案
您正在研究的算法的工作方式恰恰相反。如果字典是[MOSCOW][COLA]
,输入字符串是CA
,那么算法会告诉你MOSCOW
的所有位置CA
,以及 COLA
在 CA
中的所有位置。
现在,一个特定的状态(或者,Node
,如链接的代码所称),具有类似以下的含义:“我们可能就在唯一的 C
在 COLA
中,但我们绝对不在 MOSCOW
中间的任何地方”。 (这可能是在 CA
第一个字符之后访问的节点。)
在搜索不同的输入(例如 MOSCOLONI
)时,更容易看出算法的强大功能。就在看到 L
之前,当前状态意味着“我们可能将 5 个字符放入潜在的 MOSCOW
,或者将 2 个字符放入潜在的 COLA
” 最重要的是,状态会同时查看所有字典单词;事实上,当您考虑重复字符时,甚至可以进入所有单词的所有位置。
关于algorithm - 如何使用 Aho-Corasick 在给定的字符串集中查找一段文本?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11541524/