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.

I went about and implemented your suggestions, but it still gets TLE. Although now, it does take up less memory (only 79MB total). As for your first suggestion, I don't really need to save that space so I stuck with using

`vector<int> repeats[MAX_N]`

. In addition, I also reverted`scanf`

and`printf`

to`cin`

and`cout`

since it made no difference when testing it with large cases on my own computer. Is there a trick I'm missing in Aho-Corasick, or should I approach the problem differently, maybe using Suffix Tree?Here is my updated code: http://ideone.com/3P7XIj

Thanks for your help.

I don't undesrtand what is array "repeats". I think it can be very large and slow. use bitmasks.

`if(aho[idx].children.count(val) > 0) return aho[idx].children[val];`

the is two searches, but you need only one.3

scanf&printfis faster thancin&coutalso you can store trie using hash-table, it is fast enough. code

UPD:thre is a bug at line 81. has to be`int hp = hash(parent, val);`

can someone tell why i'm getting wa, used string hashing link to code: https://ideone.com/oRX1SS

Firstly the strings will also contain numeric characters and secondly you have to consider 'A' and 'a' as different character.