Hello,
I have a clear idea of implementing Suffix Links and I know how to build suffix links efficiently. I'm stuck with Output links, that is how to print the matched strings?
Suppose we have patterns:
i & in & tin & sting and the given string is sting
We miss both tin and in because each is a proper suffix of stin (Because suffix link of stin goes to n in tin and suffix link of n in tin goes to n in in).
How do we address this?
Could someone share Implementation details of Aho-corasick automata?
Thanking you in Advance.
Hi, here is my implementation.
First of all, thank you. Your code is Beautiful.
I have two things to ask
There was a comment that finish is vector vector . Which I think is not needed.
In case of repeated patterns, I don't think that your code is printing them. But one thing we can do is that, just do a linear search over all the patterns which we are going to match and print the same output if it was seen earlier.
Thank you.
Thanks.
Well, actually what I mean with the comment is if you have 2 patterns being the same. You will print all that is in finish in that node (So only have o change the way of printing), that's why Vector vector. Otherwise only vector is enough.
For future readers, the node 0 is never used. it is used as "null", so the code is a little shorter.
Also for future readers, get_fail function is exactly similar to KMP string pattern matching algorithm. update_out is the function which takes care of output links which I have mentioned.
I would like to take an opportunity to see a red coder's implementation.
Thank you.