Tobby_And_Friends's blog

By Tobby_And_Friends, history, 19 months ago, ,

I just learned about hashing and tried to solve this problem using the technique. My idea is I will pre-process _hash array with the hash values and afterwards I will just extract hashes of all the k-length strings and keep that in a map. Afterwards, I just output the size of the map. Any help to identify my mistake is really appreciated.

•
• -6
•

 » 19 months ago, # |   +6 well, your solution is correct but this isn't the way you can get the hash of a substring from L to R the problem is that you can't do something like hash(l,r) = (hash[r] - hash[l-1]) / pow(base,l-1); because while you're using module, you can't divide and get the same result before multiplication to solve such a problem you have to use either the mode inverse to get the correct result or you have to use segment tree and in each node(l,r,index) store the hash of the substring from l to r then you can get the correct hash from L to R without need of division
•  » » 19 months ago, # ^ |   -8 Your formula is not right.
•  » » » 19 months ago, # ^ |   +7 -_- Ok, then solve it by your own maybe I'm wrong of course, but you don't have the right to tell me that I'm wrong without explanation instead of thanking me btw, I didn't give you any "formula" in my above comment
 » 17 months ago, # |   0 You can use the modular hash or polynomial hash That solves the problem I recommend the modular hash.