Aho-Corasick与真子串

Question

我正在尝试理解aho-corasick字符串匹配算法。假设我们的模式是abcd和bc。我们最终会变成这样的树

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

虚线表示故障函数。

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

Answer 1

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

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

Answer 2

如果有一个字符串以此节点结尾，则必须将节点标记为really_final。在您的示例中，这样的节点是"abcd“和"bc”。在此之后，您必须计算节点的最终状态:如果为really_final，则node为final，或者node by failure function为final。因此，"abcd“、"bc”和"abc“将是最终结果。

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

Answer 3

设置AhoCorasick树的一部分是设置指针，如果下一个字符不匹配，指针会告诉您在树中的哪个位置。例如，如果你按照你画的树中的序列abcq，你需要从abc位置跳到bc位置，看看在bc下面是否有q。您可以使用此传递来设置另一组指针，告诉它在发出abcd匹配的信号后通知它bcd上的匹配，依此类推。

在写这篇文章的过程中，我发现http://www.cs.helsinki.fi/~jjaakkol/sgrep.html上的sgrep源代码非常有用。据我所知，sgrep做的不仅仅是AhoCorasick，还有一个AhoCorsick实现作为它的一部分。