wallcrawler's blog

271D-Good Substring!! Can't this problem be solved with single hash as in Rabin-Karp Rolling hash!! HELP NEEDED!!
By wallcrawler, history, 8 years ago, In English

I was solving this problem with the use of single hash and got wrong answer which means conflicts are arising. I've seen other users submission, they've solved it using double hashes, so I was wondering that can't this problem be solved using single hashing. Link to my submission:

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Single Hash : http://codeforces.me/contest/271/submission/37988095

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Possibility of collision , you can not use int32 modulo, it is not safe for u. If it will be helpful, my solution uses single prime modulo 261 - 1.

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

    Thank you so much!! please could you elaborate further how did you reached the conclusion for collision probability!! Thanks :)

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      I writed tutorial about rolling hash for beginners, see Minimizing the probability of collision. In this problem we need to compare each pairs of strings in set of n(n + 1) / 2 strings, so it is n4. Maybe in this problem we need to count only compares strings with equal length, maybe someone will help to accurately assess this.

      → Reply