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

Question

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

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

这是代码的链接。

Answer 1

您正在研究的算法的工作方式完全相反。如果字典是[MOSCOW][COLA]，输入字符串是CA，那么算法会告诉你MOSCOWin 的所有位置，以及inCA的所有位置。COLACA

现在，一个特定的状态（或者，Node正如链接代码所称的那样），其含义类似于：“我们可能就在唯一C的 in之后COLA，但我们绝对不是在中间的任何地方MOSCOW”。（这可能是在第一个字符之后访问的节点CA。）

当搜索不同的输入时，更容易看到算法的威力，例如MOSCOLONI。就在看到 之前L，当前状态将意味着“我们可能将 5 个字符变成一个潜在的MOSCOW，或者 2 个字符变成一个潜在COLA的”，重要的是状态会同时查看所有字典单词；事实上，当您考虑重复字符时，甚至进入所有单词的所有位置。