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.