darkshadows's blog

String hashing tutorial for beginners
By darkshadows, 10 years ago, In English

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 :)

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool, thanks!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

not good at all

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hey, thanks for feedback :) Can you help me make it good?

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a cool problem that can be solved using hashing.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks

→ Reply