Блог пользователя m.h

!! How to solve Hashing problems
Автор m.h, 10 лет назад, По-английски

Hi :)

In recent Codeforces contests , we see many problem with "Hashing" tag ! so I decide to learn Hashing algorithms and formula !

What must I do ?

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

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

Hashing = String in Base X Mod Y
X and Y are integers you have to choose i choose X = 29 or X = 43 and i choose Y as 1e9 + 7 or 1e15 + 7
or whatever what is bad about it is that two strings can have the same mod which is unlikely
you can easily get hash of strings in O(1) with preprocess of O(n) which isnt hard to think of
Good luck

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

    what is X and Y?

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

      some variables you choose?

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

      Y should be a prime (random or at least unrelated to the test data). Y should be greater than n^2, where n is the number of strings you are planning to hash.

      X should be a integer between your alphabet size and Y-1. Code is easier to write if X*Y conveniently fits into your integer data type.

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

Read this code. it can be helpful.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

http://threads-iiith.quora.com/String-Hashing-for-competitive-programming Have a look at this.

→ Ответить