Not-Afraid's blog

Hack my solution which uses Rolling Hash for Cses problem "Finding Periods"
By Not-Afraid, history, 4 years ago, In English

I was solving this problem from CSES. I used modulo $$$2$$$31-1 and was using % operator while calculating hash. It took $$$540ms$$$. Then i tried using unsigned int for calculating hash which implicitly uses modulo $$$2$$$32 if the calculation overflows or underflows and the runtime reduced to 240ms. So, i want to know if i can use my Rolling hash with unsigned int(and is it safe to use) in CF rounds(because i am always afraid of getting hacked while using Rolling Hash).
I uses Rolling Hash more often than string algorithms(if problem can be solved by Rolling hash). Even i use Rolling Hash + binary search to find longest palindromic substring because i don't really understand Manacher's Algorithms.
So, can anyone hack my solution or tell me how much probability this hash has of being hacked during a CF round?

Solution using $$$mod$$$ = $$$2$$$32.
Solution using $$$mod$$$ = $$$2$$$31-1.

  • Vote: I like it
  • +9
  • Vote: I do not like it

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

Since you are using randomization it is very hard to hack the solution with $$$mod=2^{31}-1$$$

But the solution with $$$mod=2^{32}$$$ can be hacked very easily. A countercase of length $$$2048$$$ can be generated which will work on all bases simultaneously. Simple Verdict: Do not use hash with overflow.

Zlobober has described how you can generate the anti-hash test in his blog

(He has described it for $$$mod=2^{64}$$$ but it is obvious that if 2 strings are congruent modulo $$$2^{64}$$$ they are also congruent modulo $$$2^{32}$$$.)

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

    Oh, now i see my solution's (with $$$mod$$$ = $$$2$$$32) verdict changed from AC to WA on Cses.
    Thank you for your response. I got your point.

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

    can we do this question using KMP?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, it is a possible to solve this using KMP:

      Link to code: https://cses.fi/paste/91785ee2b5f0dd262517f4/

      HINT:

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

      You can use Z-function also.

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it guranteed that your base b, and b, generated at run time will always be prime?

→ Reply