Here's the problem: SUB_PROB
I'm having trouble getting my solution to run in time, even though my algorithm should pass. If you didn't already read the problem statement, it asks you to check whether or not words exist in a piece of text. I'm currently using Aho-Corasick to solve the problem. Basically, I build up the search trie first in O(N*S), and then search through the text once in O(M). This should add up to a O(M + N*S) algorithm, which by my calculations — should AC.
Here is my code: OLD http://ideone.com/ndQcN4 OLD
EDIT — HERE IS UPDATED CODE: http://ideone.com/3P7XIj
Note: I had to split up the query strings into 3 batches since my trie would exceed the memory limit otherwise.
Is my algorithm flawed, or is my implementation not optimal. And if it is the latter case, what can I do to speed up the algorithm. I have already removed all recursive methods in exchange for iterative ones, so I don't know how I can speed it up further. Thanks.