ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1423. String Tale

WA8 Rabin–Karp and AC with KMP
Posted by Zura Isakadze [Tbilisi SU] 27 Jul 2011 20:10
any idea what could be my mistake? i'm using
i=n; i< 2n; i++
h2=((mod + h2 - dn * a[i-n] % mod) * d % mod + a[i]) % mod;

where d=256, dn=d^(n-1) mod=10^9+9
Re: WA8 Rabin–Karp and AC with KMP
Posted by waterlink 19 Aug 2011 17:46
i had WA8 with hashes, i had maxn = 250100, but it must be doubled for algo and it passed with 500100
Re: WA8 Rabin–Karp and AC with KMP
Posted by MOPDOBOPOT (USU) 26 Jul 2012 22:31
Boyer-Moor algorithm gets TL6 - it works slower than naive substrings search!
AC with KMP
Re: WA8 Rabin–Karp and AC with KMP
Posted by Aman 5 Apr 2017 22:20
Definately hashes are faster than other algo's. I also implemented using hased and was able to solve this string problem.
http://www.techcrashcourse.com/2015/05/c-programming-strings.html
http://www.techcrashcourse.com/2014/10/c-program-find-string-length.html
http://www.techcrashcourse.com/2014/10/c-program-find-palindrome-string.html

Edited by author 05.04.2017 22:22