RNR's blog

Aho-Corasick Automata — Implementation [Doubt,Help needed]
By RNR, history, 7 years ago, In English

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.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, here is my implementation.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    First of all, thank you. Your code is Beautiful.

    I have two things to ask

    1. There was a comment that finish is vector vector . Which I think is not needed.

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I would like to take an opportunity to see a red coder's implementation.

Thank you.

→ Reply