### gautam94's blog

By gautam94, 6 years ago, ,

I was reading about hashing from here and I am unable to understand the part about calculation of hash of a substring. I am calculating the hash of the entire input string in this way : h (S) = S [0] + S [1] * P + S [2] * P ^ 2 + S [3] * P ^ 3 + ... + S [N] * P ^ N

Suppose P = 31 and a = 1, b = 2, c = 3 and so on. Then for the input string abcdab, h[0] = 1, h[1] = 32, h[2] = 2915, h[3] = 122079, h[4] = 1045600, h[5] = 58303902. Now from these values, how can I calculate h[0..1] or h[3..5]?

• +6

 » 6 years ago, # | ← Rev. 3 →   +6 Let's store suffix hashes instead.We can now calculate hashes like that: h[i] = h[i + 1] * p + s[i]So, we want to find h[l..r]. Let len = r - l + 1Let's write h[l] and h[r + 1]: h[l] = s[l] * p^0 + s[l + 1] * p^1 + s[l + 2] * p^2 + ... + s[r] * p^(len - 1) + s[r + 1] * p^len + ... h[r + 1] = s[r + 1] * p^0 + s[r + 2] * p^1 + ... h[r + 1] * p^len = s[r + l] * p^len + s[r + 2] * p^(len+1) + ... h[l] - h[r + 1] * p^len = s[l] * p^0 + s[l + 1] * p^1 + s[l + 2] * p^2 + ... + s[r] * p^(len - 1) That's exactly what we need.
•  » » 6 years ago, # ^ |   0 Thanks for replying. Can you also tell me how can I use this for longer strings, say len = 10000. P^len will not fit in 64-bit int and I read this which suggests that we shouldn't do calculations mod 2^64. So, what mod should I use and how can I calculate hash of a substring when doing calculations mod some number?
•  » » » 6 years ago, # ^ |   +6 You should always use a prime modulo, for example, 10^9 + 7 or 10^9 + 9. You can do all the operations by that modulo. Just calculate powers of p by that modulo, all calculations will be fine.BTW, when you substract 2 numbers by modulo, you can get a negative number in result. If you use just a % b, in many programming languages it would be negative. For example you can use cout << -3 % 2;, it'll output -1, but you would expect 1. So, the best way to prevent negative numbers is using (a % b + b) % b. For example a = -3, b = 2: (-3 % 2 + 2) % 2 = (-1 + 2) % 2 = 1 % 2 = 1
•  » » » » 6 years ago, # ^ |   0 can you explain where i have to use (a % b + b) % b in this code http://codeforces.com/contest/182/submission/6734689 i think my error is because of this.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 So, we want to know, what is remainder if we divide a by b. As you know, mathematical remainder always belongs to the range of [0, b)So, if we write a % b, we expect to get the remainder. If a >= 0 we'll indeed get the remainder. But if a < 0 we'll not get the remainder (in most languages: C++, Java, but not Python). But actually, if we add b to this, we'll get the remainder (it will be in range (-b, 0]).For example: a % b = [what we get in C++] (what the remainder actually is) -4 % 5 = -4 (1) -153 % 42 = -27 (15) -89 % 2 = -1 (1) -88 % 2 = 0 (0) So, if we write a % b + b, we'll always get a positive integer. In case of negative a, it will be the remainder. In case of a non-negative a, it will be r + b. To get a true remainer, we'll write (a % b + b) % b. This will work for all positive values of a.
•  » » » » » » 6 years ago, # ^ |   0 hey thanks a lot for replying. i understood your comment but can you please tell the reason the code posted in this comment http://codeforces.com/blog/entry/12145#comment-171463 is giving negative hashes for some substrings. thanks.
•  » » » » » » » 6 years ago, # ^ |   0 someone please answer this. i have been working on this problem since a long time..is the hashing technique correct?
•  » » » » » » » » 6 years ago, # ^ |   0 You can use unsigned type , and forget about negativehere my examplehttp://community.topcoder.com/stat?c=problem_solution&rm=320487&rd=15840&pm=12967&cr=22853961
•  » » » » 6 years ago, # ^ |   0 for some substrings i am getting negative hash values even when i am using the exact same method as told by you but instead i am storing hashes of prefix instead of suffix as told by you in the top comment. see this http://ideone.com/DVSNkh
•  » » » » 7 months ago, # ^ |   0 Thank you very much, this comment was what I needed
•  » » » 6 years ago, # ^ |   0 You can also use a pair of hashes, both of which are computed modulo a different prime. That way you get much better collision resistance and you don't need to multiply 64-bit numbers.
•  » » » » 6 years ago, # ^ |   0 can you please tell wy i get negative value for some hashes? http://ideone.com/OgspSn dfferent base and MODs give different results.some give negative values some dont. why is it so and how can i get rid of this? this one's same as previous code but with different MOD http://ideone.com/HWtRxk but even this gives WA 3.
•  » » » » » 6 years ago, # ^ |   0 What? No, I'm not going to debug your code. But chances are good that you have an overflow in there.
•  » » » » » 6 years ago, # ^ |   0 #comment-171465Try writing separate function for calculating x % MOD
•  » » 6 years ago, # ^ |   0 suppose we have this: h[k] means hash of substring [k, N] can we get hash(l, r) in O(1)?
•  » » » 6 years ago, # ^ |   +5 Of course! o.0Just store powers of p! Now the result will be h[l] - h[r + 1] * ppow[r - l + 1]
•  » » » » 6 years ago, # ^ |   +3 thanks.
•  » » » 6 years ago, # ^ |   +3 Here's the implementation in CPP.
•  » » » » 6 years ago, # ^ |   +3 sameAnti-hash test is coming for you, so don't forget to make all the calculations by some modulo!Here's my implementation: struct SingleHash { vector suf, b; int mod; SingleHash(string s, int base = 153, int _mod = 1000000009) { int n = s.length(); suf.assign(n + 1, 0); // suf[n] = 0 b.assign(n + 1, 0); b[0] = 1; b[1] = base; mod = _mod; for (int i = n - 1; i >= 0; --i) { suf[i] = (s[i] + (ll)suf[i + 1] * b[1]) % mod; } for (int i = 2; i <= n; ++i) { b[i] = (ll)b[i - 1] * b[1] % mod; } } int substr(int l, int r) const { // [l, r] ll v = suf[l] - (ll)suf[r + 1] * b[r - l + 1]; v %= mod; v += mod; v %= mod; return v; } }; 
•  » » » » » 6 years ago, # ^ |   0 I think this one's correct too. Anyways, thanks a lot for our help. Can you also suggest a few problems that can be solved by hashing?
•  » » » » » » 6 years ago, # ^ |   0 the second one (with #define BASE 163) is the correct way to do it. having said that, ur first code (despite not having MOD) was "right" because . ur second code wouldn't work without MOD as .
•  » » 6 years ago, # ^ |   0 what if h[l] lesser than h[r+1] * p^len?? i will obviously get negative value.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I've already wrote about it, do you support reading the text?
•  » » » » 6 years ago, # ^ |   0 sorry for that. the comment you pointed to was posted just at the same time as mine. so i didnt notice. earlier i was doubting your idea but after checking it and analyzing the problem i have concluded that u are correct. i have finally got AC. thanks a lot for this. now i will be able to solve hashing problems. thanksssssssssss. :D
•  » » 20 months ago, # ^ |   0 Great method !