| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | SecondThread | 145 |
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