字符串哈希

概念讲解

什么是字符串哈希？

将字符串映射为一个整数，用于快速比较字符串。

多项式哈希

$$H(s) = \sum_{i=0}^{n-1} s_i \cdot p^i \mod M$$

实现

1234567891011121314151617const int N = 1000005;
const int P = 131;
const int M = 1e9 + 7;
long long h[N], p[N];

void init(string s) {
    int n = s.size();
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i-1] * P + s[i-1]) % M;
        p[i] = p[i-1] * P % M;
    }
}

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

双哈希

使用两个不同的 P 和 M，降低冲突概率。

123pair<long long, long long> getDoubleHash(int l, int r) {
    return {getHash1(l, r), getHash2(l, r)};
}

考点分析

初赛考查方式

1. 程序阅读： 哈希程序
2. 编程题： 字符串匹配

常见考点

• 多项式哈希
• 子串哈希
• 双哈希

例题精讲

例题 1：子串比较

题目： 判断两个子串是否相等。

解答：

比较哈希值：getHash(l1, r1) == getHash(l2, r2)

练习题

1. 字符串哈希的作用？

2. 为什么用双哈希？

3. P 和 M 怎么选？

易错点

⚠️ 注意：

1. P 选质数（如 131）
2. M 选大质数（如 1e9+7）
3. 双哈希降低冲突
4. 注意取模