Aho-Corasick Automata — Implementation [Doubt,Help needed]

Revision en1, by RNR, 2018-01-30 20:33:23

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.

Tags aho-corasick, automata, string match, string algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English RNR 2018-01-30 20:33:23 666 Initial revision (published)