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

Автор MrArM, 11 лет назад, По-английски

Hi , HappyNewYear ;)

I saw some problem that need hashing to solve , Such as 271D - Good Substrings and 127D - Password .

So I decided to learn this data structure !

I tried to find it by google but I can't find any intelligible tutorial .

Can anyone help me with any helpful tutorial ?!

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks , But it's really short and especially about implementation there is nothing :-??

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

Do you know hashing on strings? It's not same as hashtable and essential to solve problems you mentioned.

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

I don't think you need a hash-table itself; it's already implemented in most common programming languages anyways. You just want to be able to use simple hashing.

The whole idea behind hashing strings is that you convert a string (slow comparison function) into an integer, and instead of comparing the whole strings for equality, you just compare their hashes. Classic polynomial hash is the most common:

where $p$ and M are suitably chosen numbers; for me, M = 109 + 9 and p = 999983 (largest prime below 106) work well.

All you need to be able to do is compute a hash (using classic modular arithmetic) and compare hashes instead of whole strings.

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

As a comment, both mentioned problems can be solved without hashing strings under given constraints. And you might prefer solutions not involving hashing in order to avoid arguing later whether it is a good practice to add anti-hash tests to test suite.

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

I found this paper useful to learn hashing http://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

here you can find a good tutorial e-maxx site

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Google Translate? Seriously? I mean, I often find the GT'd text harder to understand than the original one... even in languages which I don't know :D

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

here is my code for this question which i submitted while ago 4917199 . u just need a base and a prime. In this problem single hashing worked well but in several cases double hashing may be required. Second question is totally different from this one. In the hashing I used for first problem, it pre-computes in O(n^2) and answer each substring in O(1) but in second One n = 1e6. There is a way to hash an string by O(n) and answer each substring by O(1) by using partial sum. For each position i in string, u have to find biggest value for x such as hash(substr(i,x)) == hash(substr(0,x)). you can binary search on x. This will work in O(nlgn)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    I think you don't need to use a module because when you calculate the hash value the integer multiplication is in module 2^64 if you are using long long. this is my solution 5617947

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      I recall a note from one tutorial:

      whoever uses 2^32 will get beaten up by Chuck Norris

      In other words, some moduli can be risky. Supposedly, as I haven't really encountered my hashes failing.