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?
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.