字符串哈希

字符串哈希

字符串哈希函数

$$
Hash(s) = (\sum_{i = 1}^{n}{c_i * base^{n - i})}\quad mod \quad p)
$$

字符串s任意字串的哈希值

$$
Hash(s_{l, r}) = (a[r] - a[l - 1] * base^{r - l + 1}\quad mod \quad p)
$$

代码实现

int base = 101, p = 9999971;
int base2 = 131, p = 9999973;
int Hash(char s[], int n) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = (res * base + s[i] - 'a') % p;
    }
    return res;
}
int calc_substr_hash(int l, int r) {
    int res = a[l - 1] * pow(base, r - l + 1) % p;
    return (a[r] - t + p) % p;
}