Aho Corasick algorithm
aho-corasick, algorithm
Solution
You probably won't gain a good understanding of the Aho-Corasick algorithm from reading a little bit of pseudocode. Unless you understand the state transition table, the algorithm will make no sense at all.
There's a decent explanation along with an animation at Aho-Corasick implementation and animation.
The original paper, Efficient String Matching: An Aid to Bibliographic Search(PDF), is well written and understandable, and the pseudocode examples are pretty easy to convert to working code. It'll take a little study, but you should have a good understanding after you read the paper, think about it a bit, and then read it again.
Problem
I am not able to understand the below algorithm which is used for string pattern matching using Aho-Corasick alg. ``` Procedure AC(y,n,q0) INPUT: y<-array of m bytes representing the text input (SQL Query Statement) n<-integer representing the text length (SQL Query Length) q0<-initial state (first character in pattern) 2: State <-q0 3: For i = 1 to n do 4: While g ( State, y[i] = = fail) do 5: State ← f (State) 6: End While 7: State ← g(State,.y[i]) 8: If o(State) then 9: Output i 10: Else 11: Output 12: End If 13: End for 14: End Procedure ```