I was trying this question : Question link
Its a classical question which asks to find a largest common substring of two string. Expected solution is to binary search on the length of required substring and check if the hash values of two substrings collides. I’ve implemented the same but getting wrong ans. Can someone help me in debugging?
Code : link
The input strings have only uppercase characters but you are using x[i]-'a'+1 as your hash coefficient which makes the above value always negative. I guess what you intended is x[i]-'A'+1, however you can even use just x[i].
Correcting all instances of 'a' to 'A' still gives WA on a later test case, which is probably due to a hash collision. A double hash should be enough to get an AC.
Thanks! I just missed that. What value of base and mod should i take for double hashing?. Is there any rule or concept behind the choice?
Got AC with Base=1000009 and M1=1000000007 , M2 = 1000000321.
But using base=26,31,101 was getting WA. What is an ideal choice of base?
Not an expert here, but general rules for a good hash are coprime base and modulus, a large modulus, and a base not smaller than alphabet size. You can refer to this pdf for more details and explanations.
