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

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

Can someone provide me some resource or code for fast hashing that can be used in topcoder SRM's/Codeforces rounds. OR I have to use set/map for hashing purposes.

Suggestion Welcome For: In what kind of problems hashing to be used.

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

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

Sometimes you face a string processing problem for which you have the correct idea, but implementing it might not be so easy. In some of these cases, you can find a much easier to implement algorithm using hashing. These algorithms don't always give correct answer, but their probability of giving wrong answer is very low.

The simplest example is string matching, where you have to find a string inside another string. Well, you can use the KMP algorithm, which is fast enough, and easy to implement if you have enough practice. There's an alternative using hashing: Rabin-Karp algorithm. You probably should know it so you can invent more powerful algorithms for more difficult problems.

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

What you're looking for with strings is most likely polynomial hashing. If you have a string (in which we could represent the characters as numbers a[i] from the range [1,x]), its prefix of i characters has the hash

A[i]=sum(j=1..i)(a[i]*p^i)%M

where p and M are suitably selected primes (I use p close to max. string length, M as large as allowed — for strings of letters with length up to 1000000 p is the first prime below 1000000 and M is 1000000009.)

Another nice characteristic of this hash is that it works like prefix sums with precomputation of power of p.

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

You can read this site Here. It's well written .