pulkit96's blog

Help needed with a TRIE question
By pulkit96, history, 11 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?
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My solution with tries

→ Reply