algorithm - 如何使用 Aho-Corasick 在给定的字符串集中查找一段文本？

Question

我有 Aho-Corasick 算法的代码。但是我仍然不明白在给定字符串列表中搜索文本时如何在查找过程中使用状态信息。

例如，我有一个字符串列表 [MOSCOW][COLA]，现在我需要确定 CA 是否在列表中，如果是，那是什么它的位置？

这是一个link to the code .

Answer 1

您正在研究的算法以完全相反的方式工作。如果字典是[MOSCOW][COLA] , 输入字符串为 CA , 然后算法会告诉你 MOSCOW 的所有位置在CA , 以及 COLA 的所有位置在CA .

现在一个特定的状态(或者，Node，正如链接代码所称)，具有类似这样的含义:“我们可能就在 C 中唯一的 COLA 之后，但我们肯定不在 MOSCOW 中间的任何地方”。 (这可能是在 CA 的第一个字符之后访问的节点。)

在搜索不同的输入时更容易看到算法的强大功能，例如 MOSCOLONI .就在看到 L 之前，当前状态将意味着“We might be 5 characters into a potential MOSCOW , or 2 characters into a potential COLA ”一次;事实上，当您考虑重复字符时，甚至可以进入所有单词的所有位置。