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

Need help in Aho-Corasick+dp+binary search problem
Автор dunjen_master, история, 6 лет назад, По-английски

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!!

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

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

LOL...

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить