Tobby_And_Friends's blog

SPOJ ADACLEAN — Ada and Spring Cleaning (Solution using hashing)
By Tobby_And_Friends, history, 8 years 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

Comments Comments (3)
| Write comment?
»
8 years 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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Your formula is not right.

    → Reply
    • »
      »
      »
      8 years 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

      → Reply