Блог пользователя inception_95

Автор inception_95, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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 :)

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +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.