algorithm - Aho-Corasick 和适当的子串

Question

我试图理解 aho-corasick 字符串匹配算法。假设我们的模式是abcd和bc。我们最终得到一棵这样的树

       []
       /\
    [a]..[b]
    /  :  |
   [b].: [c]
    |     :
   [c].....
    |
   [d]

虚线表示失效函数。

现在假设我们输入字符串abcd。这将跟随树并检测匹配“abcd”，但是，据我所知，bc不会报告匹配。我误解了算法吗？

Answer 1

如果该节点中有一个字符串结尾，则必须将节点标记为 real_final。在您的示例中，此类节点是“abcd”和“bc”。在它之后，您必须计算节点的最终状态：如果节点是真的_最终或失败函数的节点是最终的，则节点是最终的。因此，“abcd”、“bc”和“abc”将是最终的。

换句话说 - 如果某个模式在这里结束，或者某个最终节点可以从当前节点通过故障链接到达，则节点是最终节点。

Answer 2

Artem 的回答是正确的，但可能不是很清楚。基本上您需要做的是：每次到达一个新节点时，检查从该节点开始并由故障链接组成的整个路径，并在该路径上找到匹配项。（这不会改变您当前的位置）。在您的示例中，您将检查路径 b->b （未找到匹配项）和 c->c （找到匹配bc项）。

请注意，出于效率原因，您需要在每个节点缓存“下一个匹配”的值。也就是说，如果您检查从 node 开始的路径u并在几个步骤后找到匹配的节点v，请记住该值next_match[u] = v，以便下次必须检查此路径时，您可以直接跳转到v.

Answer 3

设置 AhoCorasick 树的一部分是设置指针，如果下一个字符不匹配，则告诉您在树中的位置。例如，如果您按照绘制树中的序列 abcq 进行绘制，则需要从 abc 位置跳转到 bc 位置，以查看 bc 下方是否有 aq。您可以使用此通行证设置另一组指针，告诉它在发出 abcd 上的匹配信号后，在 bcd 上发出匹配信号，依此类推。

在编写它时，我发现http://www.cs.helsinki.fi/~jjaakkol/sgrep.html上的 sgrep 的来源非常有帮助。据我所知，sgrep 不仅仅是 AhoCorasick，它还包含一个 AhoCorsick 实现。