inception_95's blog

ADAJOBS — Ada and Jobs
By inception_95, history, 7 years 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

Comments Comments (9)
| Write comment?
»
7 years 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

→ Reply
  • »
    »
    7 years 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?

    → Reply
    • »
      »
      »
      7 years 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 :)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hello,
        I've Implemented Aho-corasick algorithm to solve this problem but I'm getting WA after test case 14. Here is my code

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think it stops running as soon as it faces WA, RTE or TLE.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +12 Vote: I do not like it

              Try WA1 and you will just notice.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                yup you were right.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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!

                  → Reply