字符串哈希实现原理

给定一个字符串 s = abcdefg，要将字符串 S 看成是一个 B 进制数；

B 的最佳取值为：\(233、133、13331\)，由于字符串 S 的哈希值非常大，要对 M 取模；

M 的最佳取值为 \(10 ^ 9 + 7、、10 ^ 9 + 9、2 ^ 64\)；

不太推荐使用自然溢出的做法。

自然溢出

typedef unsigned long long ULL;
ULL B = 13331, R[N], H[N];
int n;
string s;

void init()
{
    R[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        R[i] = R[i - 1] * B;
    }

    for (int i = 1; i <= n; i ++)
    {
        H[i] = H[i - 1] * B + s[i - 1];
    }
}

ULL get_hash(int l, int r)
{
    return H[r] - H[l - 1] * R[r - l + 1];
}

ULL mul_rk(ULL x, int k)
{
    return x * R[k];
}

对质数取模

typedef unsigned long long ULL;
ULL B = 233, R[N], H[N], M = int (1e9 + 7);
int n;
string s;

void init()
{
    R[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        R[i] = R[i - 1] * B; R[i] %= M;
    }

    for (int i = 1; i <= n; i ++)
    {
        H[i] = (H[i - 1] * B + s[i - 1]) % M;
    }
}

ULL mul_rk(ULL x, int k)
{
    return (x * R[k]) % M;
}

ULL get_hash(ULL H[], int l, int r)
{
    return (H[r] - mul_rk(H[l - 1], r - l + 1) + M) % M;
}