Calculate Longest common substring using hashing + binary search

I was going through the editorial

When they try to calculate hash for a specefic segment in a string using the following logic

Hash(S[l..r]) = (Hash(S[0..r]) - Hash(S[0..l-1]) * MAGIC^(r-l+1)) % MOD

How this relation is working ?? what is the logic behind multiplication with MAGIC^(r-l+1) ??
As i observed , the logic should be ,

 Hash(S[l..r]) = (Hash(S[0..r]) - (Hash(S[0..l-1]* MAGIC^(r-l+1)))%MOD +MOD) % MOD 

Can someone plz explain the same ??

Go through this link link text

1 Like

Hey , I got my mistake , thanks for the reply :slight_smile: