inception_95's blog

By inception_95, history, 4 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    thanks! what can I do now to reduce time? Can you provide me with a faster implementation?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 :)