I have implemented Aho-Corasick algo for the question http://www.codechef.com/AUG13/problems/LYRC/
and I am unable to find where my code is going wrong, can somebody help me find the case where its going wrong???
my code link : http://ideone.com/ZAIpye
In PrepareAutomaton(), every P[i] is added to the trie, child[i][j] stores the node index of child of i with character index j(which is written in function int Index(char)).
Process(int i) processes S[i] character by character. lsp[i] is the node index of longest suffix which is also prefix of string from root to node i, for every character in S[i] we try to find longest suffix of substring S[i][0…j] which is present in the trie and increase the count of that node, now we should increase every suffix of this node that is also present in the trie as it is present in the string S[i],
got this by first sorting all nodes by distance from root and moving backwards from farthest node, increase matches[lsp[i]] by matches[i] and make all the ans[j] such that string from root to node i is P[j] equal to matches[i].
Did I miss anything ??