Negationist's blog

By Negationist, history, 6 weeks ago, In English

Why does my rolling hash never work?

hash implementation
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Because of an integer overflow. The values for $$$h[i]$$$ can reach up to $$$B-1$$$, and multiplying that with $$$A$$$ likely causes an integer overflow.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    whats the solution to this?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      use long long

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what's happening is that the value is getting too big to be stored into "int" before you take the mod hence the problem

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i have int macroed to long long tho

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh okay.

            now suppose some index k, h[k]=(1ll<<61)-2, now suppose A=1e9, now h[k]*A would overflow long long. Do not keep the mod values so big. try to keep it upto 1e9+7 in general to avoid overflows.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              is that ok given the birthday paradox, is it still safe?

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I lowered B to 1e9+7 and unless A is very small, <10, it still fails.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                int hash2 = (h[n-1] — h[b-1]*pow[n-b])%B; this line might also lead to incorrect results as the quantity inside the brackets might be -ve and result might not be as expected, try something like: int hash2 = (h[n-1] — (h[b-1]*pow[n-b])%B+B)%B; given you handled other overflows correctly.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  what fixed it was "if(hash2<0){ hash2+=B; }" though I dont understand why because the prefix hash should be less than the original right??????

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You are taking the mod at every step. Any such inequalities are not maintained after that.