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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
  unsigned long long f = 31, p[100010], h[100010];
h<sub>i</sub> = s<sub>0</sub>x<sup>n - 1</sup> + s<sub>1</sub>x<sup>n - 2</sup> + ... + s<sub>n - 2</sub>x + s<sub>n - 1</sub>.
 
  struct Hasher {
    long long x = 31, mod = 1e9 + 7;
    vector<long long> p, h;
   
   
void buildHash(char s[]) {
    Hasher(const string &s) {
    p[0] = 1;
        p.resize(s.size());
    h[0] = s[0] - 'a' + 1;
        h.resize(s.size());
    for (int i = 1; s[i]; i++) {
        p[i] = p[i - 1] * f;
        p[0] = 1;
        h[i] = h[i - 1] + p[i] * (s[i] - 'a' + 1);
        h[0] = s[0] - 'a' + 1;
        for (int i = 1; i < s.size(); i++) {
            p[i] = p[i - 1] * x % mod;
            h[i] = (h[i - 1] * x % mod + s[i] - 'a' + 1) % mod;
        }
     }
     }
}
   
   
bool areEqual(int l1, int r1, int l2, int r2) {
    long long getHash(int l, int r) {
    unsigned long long h1 = h[r1] - (l1 ? h[l1 - 1] : 0);
        long long res = h[r];
    unsigned long long h2 = h[r2] - (l2 ? h[l2 - 1] : 0);
        if (l)
    if (l1 < l2)
            res = (res - p[r - l + 1] * h[l - 1] % mod + mod) % mod;
        h1 *= p[l2 - l1];
         return res;
    if (l2 < l1)
     }
         h2 *= p[l1 - l2];
  };
     return h1 == h2;
  }


{| width="100%"
{| width="100%"
| width=50% |
| width=50% |
h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.
Для выравнивания хеши различных подстрок домножаются на x<sup>n - 1 - L</sup>.
  struct Hasher {
  struct Hasher {
     long long f = 31, mod = 1e9 + 7;
     long long x = 31, mod = 1e9 + 7;
     vector<long long> p, h;
     vector<long long> p, h;
   
   
     Hasher(string &s) {
     Hasher(const string &s) {
         p.resize(s.size());
         p.resize(s.size());
         h.resize(s.size());
         h.resize(s.size());
Строка 34: Строка 44:
   
   
         for (int i = 1; i < s.size(); i++) {
         for (int i = 1; i < s.size(); i++) {
             p[i] = (p[i - 1] * f) % mod;
             p[i] = p[i - 1] * x % mod;
             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;
         }
         }
     }
     }
Строка 43: Строка 53:
         if (l)
         if (l)
             res = (res - h[l - 1] + mod) % mod;
             res = (res - h[l - 1] + mod) % mod;
         res = (res * p[p.size() - 1 - l]) % mod;
         res = res * p[p.size() - 1 - l] % mod;
         return res;
         return res;
     }
     }
  };
  };
 
Этот способ непригоден для сравнения участков двух строк разной длины. В данном случае хеш более левого участка следует домножать на x<sup>|L1 - L2|</sup>.
   
   
| width="10px" | &nbsp;
| width="10px" | &nbsp;
| width=50% |
| width=50% |
h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.
Для выравнивания хеши различных подстрок домножаются на (x<sup>-1</sup>)<sup>L</sup>.
  struct Hasher {
  struct Hasher {
     long long f = 31, {{Changed|1=fi = 129032259,}} mod = 1e9 + 7;
     long long x = 31, {{Changed|1=xi = 129032259,}} mod = 1e9 + 7;
     vector<long long> p, {{Changed|pi,}} h;
     vector<long long> p, {{Changed|pi,}} h;
   
   
Строка 64: Строка 79:
   
   
         for (int i = 1; i < s.size(); i++) {
         for (int i = 1; i < s.size(); i++) {
             p[i] = (p[i - 1] * f) % mod;
             p[i] = p[i - 1] * x % mod;
             {{Changed|1=pi[i] = (pi[i - 1] * fi) % mod;}}
             {{Changed|1=pi[i] = pi[i - 1] * xi % mod;}}
             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;
         }
         }
     }
     }

Версия от 01:41, 7 декабря 2021

hi = s0xn - 1 + s1xn - 2 + ... + sn - 2x + sn - 1. 

struct Hasher {
    long long x = 31, mod = 1e9 + 7;
    vector<long long> p, h;

    Hasher(const string &s) {
        p.resize(s.size());
        h.resize(s.size());

        p[0] = 1;
        h[0] = s[0] - 'a' + 1;

        for (int i = 1; i < s.size(); i++) {
            p[i] = p[i - 1] * x % mod;
            h[i] = (h[i - 1] * x % mod + s[i] - 'a' + 1) % mod;
        }
    }

    long long getHash(int l, int r) {
        long long res = h[r];
        if (l)
            res = (res - p[r - l + 1] * h[l - 1] % mod + mod) % mod;
        return res;
    }
};

hi = s0 + s1x + s2x2 + ... + sn - 1xn - 1.

Для выравнивания хеши различных подстрок домножаются на xn - 1 - L. 

struct Hasher {
    long long x = 31, mod = 1e9 + 7;
    vector<long long> p, h;

    Hasher(const string &s) {
        p.resize(s.size());
        h.resize(s.size());

        p[0] = 1;
        h[0] = s[0] - 'a' + 1;

        for (int i = 1; i < s.size(); i++) {
            p[i] = p[i - 1] * x % mod;
            h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod;
        }
    }

    long long getHash(int l, int r) {
        long long res = h[r];
        if (l)
            res = (res - h[l - 1] + mod) % mod;
        res = res * p[p.size() - 1 - l] % mod;
        return res;
    }
};

Этот способ непригоден для сравнения участков двух строк разной длины. В данном случае хеш более левого участка следует домножать на x|L1 - L2|.

 

hi = s0 + s1x + s2x2 + ... + sn - 1xn - 1.

Для выравнивания хеши различных подстрок домножаются на (x-1)L. 

struct Hasher {
    long long x = 31, xi = 129032259, mod = 1e9 + 7;
    vector<long long> p, pi, h;

    Hasher(const string &s) {
        p.resize(s.size());
        pi.resize(s.size());
        h.resize(s.size());

        p[0] = pi[0] = 1;
        h[0] = s[0] - 'a' + 1;

        for (int i = 1; i < s.size(); i++) {
            p[i] = p[i - 1] * x % mod;
            pi[i] = pi[i - 1] * xi % mod;
            h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod;
        }
    }

    long long getHash(int l, int r) {
        long long res = h[r];
        if (l) {
            res = (res - h[l - 1] + mod) % mod;
            res = (res * pi[l]) % mod;
        }
        return res;
    }
};

Ссылки

Теория:

Код:

Задачи:

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