algorithm - Aho-Corasick 和真子串

Question

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

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

虚线表示失效函数。

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

Answer 1

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

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