Calculate Longest common substring using hashing + binary search

general
, ,
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^(r-l+1)))%MOD +MOD) % MOD

Can someone plz explain the same ??

2

Go through this link link text

1 Like
3

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