Хеширование строк: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 21: Строка 21:
     return h1 == h2;
     return h1 == h2;
  }
  }
| width="10px" |  
| width="10px" |  
| width="50%"  |
| width="50%"  |
  struct Hasher {
  struct Hasher {
    unsigned long long f, mod, p[210], h[210];
    static const int SIZE = 200010;
    unsigned long long f, mod, p[SIZE], h[SIZE];
   
   
    Hasher() {
    Hasher(int f, int mod) : f(f), mod(mod) {
        f = 31;
        p[0] = 1;
        mod = 1e9 + 7;
        for (int i = 1; i < SIZE; i++)
        p[0] = 1;
            p[i] = (p[i - 1] * f) % mod;
        for (int i = 1; i < 210; i++)
    }
            p[i] = (p[i - 1] * f) % mod;
    }
   
   
    void buildHash(char s[]) {
    void buildHash(char s[]) {
        h[0] = s[0] - 'a' + 1;
        h[0] = s[0] - 'a' + 1;
        for (int i = 1; s[i]; i++)
        for (int i = 1; s[i]; i++)
            h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
            h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
    }
    }
   
   
    unsigned long long getHash(int l, int r) {
    unsigned long long getHash(int l, int r) {
        return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[209 - l]) % mod;
        return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[SIZE - 1 - l]) % mod;
    }
    }
  } hasher;
  } ha(29, 1e9 + 7), hb(31, 1e9 + 9);
|}
|}


Версия от 14:37, 10 июня 2018

unsigned long long f = 31, p[100010], h[100010];

void buildHash(char s[]) {
    p[0] = 1;
    h[0] = s[0] - 'a' + 1;
    for (int i = 1; s[i]; i++) {
        p[i] = p[i - 1] * f;
        h[i] = h[i - 1] + p[i] * (s[i] - 'a' + 1);
    }
}

bool areEqual(int l1, int r1, int l2, int r2) {
    unsigned long long h1 = h[r1] - (l1 ? h[l1 - 1] : 0);
    unsigned long long h2 = h[r2] - (l2 ? h[l2 - 1] : 0);
    if (l1 < l2)
        h1 *= p[l2 - l1];
    if (l2 < l1)
        h2 *= p[l1 - l2];
    return h1 == h2;
}
  
struct Hasher {
   static const int SIZE = 200010;
   unsigned long long f, mod, p[SIZE], h[SIZE];

   Hasher(int f, int mod) : f(f), mod(mod) {
       p[0] = 1;
       for (int i = 1; i < SIZE; i++)
           p[i] = (p[i - 1] * f) % mod;
   }

   void buildHash(char s[]) {
       h[0] = s[0] - 'a' + 1;
       for (int i = 1; s[i]; i++)
           h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
   }

   unsigned long long getHash(int l, int r) {
       return ((h[r] - (l ? h[l - 1] : 0) + mod) % mod * p[SIZE - 1 - l]) % mod;
   }
} ha(29, 1e9 + 7), hb(31, 1e9 + 9);

Ссылки

Теория:

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=Хеширование_строк&oldid=2308