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。