### Hepic_Antony_Skarlatos's blog

By Hepic_Antony_Skarlatos, 10 years ago,

In this problem http://www.spoj.com/problems/PLD/ , what is the best way to use rabin_karp?

To precalculate hashes,or add-delete numbers? Cause I am stuck at this 4 hours now... :(

 » 10 years ago, # |   0 Substring [l..r] is a palindrome when it equals to its reversed version. So you can precalc hashes for s and for reversed s. Then you may check for all k-substrings if they are equal to its reversed versions.
•  » » 10 years ago, # ^ |   0 The time to hash a substring,is the same with pass it with a for loop right? So instead precalculate all hashes,why not to check with naive way??Except if I calculate the hash via adding and deleting new and last character. I know How to do that in normal string,but in reversing string,I need to delete in reversing mode of rabin-karp.For example if I have "asd" as string,rabin karp says:(a*BASE + s)*BASE + d, and when I delete I says -=a*BASE^2.but in reversing string,I need to delete from the other side,so I should say: -d,and after /=BASE. That gives me strange numbers....I cant get it!!!
•  » » » 10 years ago, # ^ |   0 The time to hash a substring,is the same with pass it with a for loop right?There is a way to calculate polynomial hash of substring in O(1) with O(n) precalc. It's like prefix-sums.
•  » » » » 10 years ago, # ^ |   0 Ok,I figured out !!! Thanks for the time!!!