Hello Everyone!
I have made a video tutorial on how we can compare substrings in constant time using string hashing in C++.
I have taken the problem from Codechef May CookOff "Chef Chefina and their friendship" which can be solved using hashing.
Check it out here
Thank You!
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 171 |
| 2 | adamant | 164 |
| 3 | awoo | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 9 | orz | 145 |
| 9 | pajenegod | 145 |
compare substrings in constant time
Wow. I am really interested in how your hashing function would compute the hash of a string in O(1).
After computation,you can compare in O(1) time. Computation takes O(n).
Erm. What is your comparison algo?
I meant to check if equal or not.
So how do you check if a string is equal to another?
With the hash value also I have been following you for a while, between you and me whats your real ID? https://cp-algorithms.com/string/string-hashing.html
Oh. I see. So you hash both strings first and you compare their hash values. I think that is only useful if you are hashing a large number of strings. And that is going to be quadratic in their length, which doesn't make much sense to me.
For comparison of substrings it does make sense.What's your real ID?