inception_95's blog

By inception_95, history, 4 years ago,

The idea of the problem is to take all the queries at first, insert the strings and store the id(s) in the trie. Then when searching for the strings we look at the id and if it is less than the id of that query, that means it has been inserted before this query and so the output is "YES" or else "NO".

Can you show me where the problem is? Useful testcases will also be appreciated.

Code: Solution Code

• +5

 » 4 years ago, # |   +1 Good day to you,well if I'm not mistaken, then your search function seems to be quadratic (rest seems to go smoothly). Imho it fails for long strings + long patterns with common suffix (since you always jump all way back in the "while").Good Luck & Have Nice Day
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 thanks! what can I do now to reduce time? Can you provide me with a faster implementation?
•  » » » 4 years ago, # ^ |   +6 Guess,take look at Aho-Corrasic algorithm how it is done in near-linear time (I won't give you mine implementation, sorry, anyway I would say you seems to be on a good way (even thought I havenẗ studied your code deeply)). Imho — manage the "fail function" not to reeturn back after each "scroll"GL :)
•  » » » » 3 years ago, # ^ |   0 Hello,I've Implemented Aho-corasick algorithm to solve this problem but I'm getting WA after test case 14. Here is my code
•  » » » » » 3 years ago, # ^ |   +11 Just for your information, in SPOJ, non-AC verdict after test number doesn't indicate that that number is the test that you stuck. It just checks all tests and tells you the verdict.
•  » » » » » » 3 years ago, # ^ |   0 I think it stops running as soon as it faces WA, RTE or TLE.
•  » » » » » » » 3 years ago, # ^ |   +12 Try WA1 and you will just notice.
•  » » » » » » » » 3 years ago, # ^ |   0 yup you were right.
•  » » » » » » » » » 3 years ago, # ^ |   +1 Good day to you,try for-example following input 10 0 iyyi 0 y 0 yiiy 0 yiiyi 0 yy 0 yiii 1 y 1 iiy 1 iy 1 i Wish you a nice day!
•  » » » » » » » » » 6 weeks ago, # ^ | ← Rev. 4 →   0 Try to check your output on the below test case:40 abc1 abc0 abc1 abcOutput: YESYESbecause of the same jobs, your solution might go wrong as you might updating the index of a job.