hash小结

hash

int hash(ll x)
{
    ll t = x % N;
    while (h[t] && h[t] != x) t = (t + 1) % N;
    return t;
}

int main()
{
    fo(i, 1, n)
        x = (x * 26 + s[i] - 97) % mo;
    t = hash(x);
    h[t] = x;
}

double hash

int hash(ll x, ll y)
{
    ll t = x % N;
    while (h[t][0] && (h[t][0] != x || h[t][1] != y)) t = (t + 1) % N;
    return t;
}

int main()
{
    fo(i, 1, n)
    {
        x = (x * 26 + s[i] - 97) % mo;
        y = (y * 26 + s[i] - 97) % mo1;
    }
    t = hash(x, y);
    h[t][0] = x, h[t][1] = y;
}

hash字符串中的子串

int main()
{
    cf[0] = 1;
    fo(i, 1, n) cf[i] = cf[i - 1]  * 26; 
    fo(i, 1, n)
        qz[i] = (qz[i - 1] * 26 + s[i] - 97) % mo;
//  对于[i~j]的hash值 
    (qz[j] - qz[i - 1] * cf[j - i + 1] % mo + mo) % mo;
}

树hash

树\(hash\)用来比较树是否同构。

详见该博客