Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Tobby_And_Friends's blog

By Tobby_And_Friends, history, 22 months ago, In English,

Problem: http://www.spoj.com/problems/ADACLEAN/ Solution: http://ideone.com/TracEP Verdict: Wrong Answer

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.

 
 
 
 
  • Vote: I like it  
  • -6
  • Vote: I do not like it  

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Your formula is not right.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      -_-
      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

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use the modular hash or polynomial hash That solves the problem I recommend the modular hash.