| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
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