Aho-Corasick and Proper Substrings

Question

I'm trying to understand the aho-corasick string match algorithm. Suppose that our patterns are abcd and bc. We end up a tree like this

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

The dotted line show the failure function.

Now supposed that we feed in the string abcd. This will follow the tree and detect the match "abcd," however, as far as I can tell the match bc will not be reported. Am I misunderstanding the algorithm?

Answer 1

Artem's answer is correct, but perhaps not very clear. Basically what you need to do is: every time you arrive at a new node, examine the whole path starting from this node and consisting of failure links and find matches on this path. (This doesn't change your current position). In your example you would examine the paths b->b (no matches found) and c->c (the match bc is found).

Note that for efficiency reasons you need to cache the value of 'next match' at each node. That is, if you examine the path starting at node u and find a matching node v after several steps, remember the value next_match[u] = v so that next time when you have to examine this path, you could make a single jump straight to v.

Answer 2

You have to mark nodes as really_final if there is a string ended in this node. In your example such nodes are "abcd" and "bc". After it you have to calc final states for nodes: node is final if it's really_final or node by failure function is final. So, "abcd", "bc" and "abc" will be final.

In other words - node is final if some pattern is ended here or some final node is reacheable from current node walking by failure links.

Answer 3

Part of setting up the AhoCorasick tree is setting up the pointers that tell you where to go in the tree if the next character is not a match. E.g. if you follow the sequence abcq in the tree as you have drawn it, you need to jump from the abc position to the bc position to see if there is a q below bc. You can use this pass to set up another set of pointers to tell it to signal a match on bcd after signalling a match on abcd and so on.

In writing it, I found the source of sgrep at http://www.cs.helsinki.fi/~jjaakkol/sgrep.html very helpful. As far as I can remember, sgrep does a LOT more than just AhoCorasick, but has an AhoCorsick implementation as part of it.