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.
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}$$$.)
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.
can we do this question using KMP?
Yes, it is a possible to solve this using KMP:
Link to code: https://cses.fi/paste/91785ee2b5f0dd262517f4/
HINT:
With some pre-computation, in O(1), you should be able to check if a prefix of length 'i' is a suffix (not necessary longest length which KMP tracks by default) of the string ending at position 'j'. Then, for a prefix of length 'i', you can traverse through the entire string and see if is one of the periods in (n/i) iterations.
Overall: (n/1) + (n/2)+(n/3)+..+(n/n) leads to O(n log n)
You can use Z-function also.