Блог пользователя wallcrawler

271D-Good Substring!! Can't this problem be solved with single hash as in Rabin-Karp Rolling hash!! HELP NEEDED!!
Автор wallcrawler, история, 6 лет назад, По-английски

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:

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks mate....could you tell me one thing that in the power array you are storing powers of p = 123, why it is not overflowing since n can be upto 1500. And another thing I think I did exactly same thing as your's could you review my code for a minute pal!! Please.... Your kind help would be appreciated.

    → Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить