Hepic_Antony_Skarlatos's blog

Palindromes spoj problem
By Hepic_Antony_Skarlatos, 10 years ago, In English

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... :(

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply