pulkit96's blog

Help needed with a TRIE question
By pulkit96, history, 9 years ago, In English

Hi I recently learned about tries and tried this question---- http://mirror.codeforces.com/contest/514/problem/C this is my solution to problem ---- http://mirror.codeforces.com/contest/514/submission/12742436 I would be glad if someone could take some time and explain what might be wrong with the solution , I have tried to add necessary comments to explain my approach.

PS- I was successful in solving this question using polynomial hashing but wanted to solve this using tries.

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't see why do you get WA, but anyway it won't pass because it does O(|s|2) operations for each string and that's too slow

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

    while coding it didn't strike me , but indeed it is O(|s|**2). Thanks for pointing that out . It would be great if you can offer any other suggestions on how it can be solved using tries . Thanks again.

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

My solution with tries

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

    hi SomeRandomGuy, could you explain your solution more specifically how your Find function works, i could not decipher it from the code .

    → Reply