SSU Online Judge Problem : 284 (Grammer)

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

Автор hagu, 12 лет назад, По-английски

I was trying to solve this problem but i am getting WA on test 19. I'm not able to figure out the bug in my code.

Problem Link :- http://acm.sgu.ru/problem.php?contest=0&problem=284

I have used the approach explained here :- http://e-maxx.ru/algo/prefix_function translated version here :- http://translate.yandex.net/tr-url/ru-en.en/e-maxx.ru/algo/prefix_function

I have first computed the pie function(KMP) of the pattern to search. Then i have used the approach explained in the given link. (The Build Machine prefix function part).

This is my code :- http://ideone.com/NcBqKX

kmp, e-maxx, saratov

hagu
12 лет назад
6

Комментарии (5)

Показать архивные | Написать комментарий?

mnbvmar

12 лет назад, скрыть # |

I haven't inspected your code but I have a guess. The result doesn't have to fit inside int (and long long, either). I think a big integer implementation is required here.

→ Ответить

hagu

12 лет назад, скрыть # ^ |

← Rev. 3 →

can you explain to me your computation analysis of why it won't fit inside long long range. If you can, provide me the link to your big integer implementation.

P.S -> I tried using unsigned long long too , still the same result.

→ Ответить

mnbvmar

12 лет назад, скрыть # ^ |

30
a
16 a a a a a a a a a a a a a a a a
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
16 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
16 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
...
16 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29

Then 1 consists of 16 characters, 2 is made of 16² characters and so on; finally, 30 is made of 16³⁰ = 2¹²⁰ characters and the same number of occursnces, which is larger than 2⁶⁴. Of course, I think the result can still be slightly bigger.

I don't have any big-int implementation on my hard drive, I'm sorry :P

→ Ответить