Aho-Corasik-Youtube-Question.md

We start with the dictionary: { a, ab, bc, aab, aac, bd, ca }

And the Search String: bcaab

1. Build the Trie

Following the steps in the first video you should end up with

2. Set the Failure Nodes

Follow the step in the second video you should end up with

3. Matching

Given the trie above, we identify all matches for words in our dictionary in linear time.

Step 1. i=0

curr=root, i=0

Does curr have a child that starts with haystack[i], namely b? Yes.

We set curr = curr.children[haystack[i]] essentially curr=b and then record the output at that node. In this case, b has no output.

Increment i

Step 2. i=1

curr=b, i=1

Does curr have a child that starts with haystack[i], namely c? Yes.

We set curr = curr.children[haystack[i]] essentially curr=bc and then record the output at that node. In this case, bc outputs ["bc"].

So our matches map looks like

{ "bc": [ (i-len("bd")+1) ] } or { "bc": [ 0 ] }

increment i

Step 3. i=1

curr=bc, i=2

Does curr have a child that starts with haystack[i], namely a? No. So we fail to the failure node and try again. Essentially, curr=curr.fail, namely c

Does curr have a child that starts with haystack[i], namely a? YES!

So we update the matches map as following

{
  "a": [ (i-len("a")+1) ],
  "bc": [ 0 ],
  "ca": [ (i-len("ca")+1) ],
}

or { "bc": [ 0 ], "a": [2], "ca": [1] }

increment i.

the rest is left as an exercise to the reader...