Hi,
I have tried to explain string hashing using a few example problems for beginners. Check it out the post here: http://threads-iiith.quora.com/String-Hashing-for-competitive-programming
PS: The content in the post may seem quite naive to experienced coders :)
Cool, thanks!
not good at all
Hey, thanks for feedback :) Can you help me make it good?
I think the explanation is fantastic, but you need more applications. For example, what can I use this for besides hashing problems? (ex. suffix arrays). I would also recommend finding problems that combine more advanced techinques like DP with hashing. Your sliding window problem was good.
Here is a cool problem that can be solved using hashing.
Please can somebody explain when computing F(R) — F(L-1), why we have multiplied Hash( S|L,R| ) with pL ?
The equation according to author is F(R) — F(L-1) = Hash( S|L,R| ) * pL
F(R)-F(L-1)=P^L.s[L] + p^(L+1).s[L+1] + ... + P^(R).s[R] mul by P^(-L) to get the actual hash value of substring from l to r.
By, p^L the author might be meaning the inverse of b^L, where b is base used for calculating hashes.
Thanks