Hi,
My knowledge on String algorithms is poor so I am studying it now.
I solved 271D - Good Substrings using a Trie, but I am trying to solve it using hashing.
I am able to calculate a polynomial rolling hash and compare substrings based on the hash, but my solution is getting WA on test 8 (230797737). I am thinking this is because of collisions, since the expected answer is also pretty high.
I read a topic on double polynomial rolling hash to reduce probability of collisions. I understand that if we use two hashes of order 10^9 then probability will be less because it is equivalent to using a 10^18 modulo.
I am unable to understand how to implement it.
Can anyone help?
Please point me towards an article/blog/submission that has code on implementing it.
Thank you.