Calculate Longest common substring using hashing + binary search

binary-search
hashing
substring

#1

I was going through the editorial
editorail

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^(l)))%MOD +MOD) % MOD 

Can someone plz explain the same ??


#2

Go through this link link text


#3

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