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.
Thanks in advance.
Problem link: ADAJOBS — Ada and Jobs
Code: Solution Code
Good day to you,
well if I'm not mistaken, then your
searchfunction 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
thanks! what can I do now to reduce time? Can you provide me with a faster implementation?
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 :)
Hello,
I've Implemented Aho-corasick algorithm to solve this problem but I'm getting WA after test case 14. Here is my code
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.
I think it stops running as soon as it faces WA, RTE or TLE.
Try WA1 and you will just notice.
yup you were right.
Good day to you,
try for-example following input
Wish you a nice day!