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

Palindromes spoj problem
Автор Hepic_Antony_Skarlatos, 10 лет назад, По-английски

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

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

»
10 лет назад, # |
  Проголосовать: нравится 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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится 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.

      → Ответить