dunjen_master's blog

Need help in Aho-Corasick+dp+binary search problem
By dunjen_master, history, 8 years ago, In English

Here is the problem statement https://www.codechef.com/problems/FAVNUM Link to my solution https://www.codechef.com/viewsolution/22195079 I have tried my code on few cases and it works i am not able to find my mistake. Please help!!

  • Vote: I like it
  • -28
  • Vote: I do not like it

»
8 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

LOL...

→ Reply
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

You can write a stress test like this to help you find a testcase that the code fails on. Like this one:

32526 33790 677 23
96111730048301290
58
37089307478371
783450145
70356667677
2162727651399592
3324442792373
878583241159
906453
2
43474636528103
2522174823
2
852807225910850
7053
4
48592541395
77961771903417533
41290874568077431
13
59042931482
6593287481435
368929594505880132

The bug is in the ACA. If a state is an End of some string then all other states that contain this state as a prefix must be an end too. In the bfs for constructing the suffix links, you can just add isEnd[x] |= isEnd[f[x]] and you would get AC.

→ Reply