字符串哈希

简介

该算法通过把字符串变成一个 $p$ 进制数字（哈希值），实现将不同的字符串映射到不同的数字。计算方法是，对形如 $X_{1}X_{2} ... X_{n}$ 的字符串，将每一位上的字符 ASCII 码乘上 $p$ 的不同次方之和来计算哈希值：

$$(X_{1} \times P^{n-1} + X_{2} \times P^{n−2} + ⋯ + X_{n−1} \times P^1 + X_n \times P^0) \mod Q$$

注意：

1. 任意字符不可以映射成 $0$，否则会出现不同的字符串都映射成 $0$ 的情况，比如 A, AA, AAA ，经过上述公式计算后，字符串哈希值皆为 $0$。
2. 冲突问题：设置 $P$ 值为 $131$ 或 $13331$，$Q$ 值为 $2^{64}$，99.99% 的概率不会冲突。（经验）

举例

现在按照上述公式举例说明字符串哈希值的计算过程：

• 输入字符串为 “ABC”
• $P$ 值为 $131$
• $Q$ 值为 $2^{64}$

$$\text{Hash(“ABC”)} = (65 \cdot 131^2 + 66 \cdot131^1 + 67 \cdot 131^0) \ \text{mod} \ 2^{64} = 1124178$$

特性：字串完全匹配查询

假设现在拥有一个长度为 $n$ 的字符串，通过字符串哈希与前缀和，仅需要 $O(1)$ 的时间，即可快速知道 $[l_1, r_1]$ 与 $[l_2, r_2]$ 子串是否相同。（不需要逐字符比对）

**例如：**前缀和中下标从 1 开始。设字符串 ABCDE，若想求子串 BCD 的哈希值，即 $[4, 2]$，只需求哈希前缀 $A[4] - A[1] * P[3]$ 的值。

$$\text{PreSum}: A[i] = A[i - 1] * p + \text{String[i]} \\ \text{Query(l, \ r)} = A[r] - A[l - 1] * P[r - l + 1]$$

例题：1316. 不同的循环子字符串 - 力扣（LeetCode）

class Solution {
public:
    unsigned long long a[2010];
    unsigned long long p[2010];
    int distinctEchoSubstrings(string text) {
        int n = text.size();
        unordered_map<unsigned long long, int> res;
        memset(a, 0, sizeof a);
        p[0] = 1;
        for (int i = 0; i < n; i ++) {
            a[i + 1] = a[i] * 131 + text[i];
            p[i + 1] = p[i] * 131;
        }
        for (int i = 1; i <= n; i ++) { // 长度
            for (int l = 1; ; l ++) { // 左端点
                int r = l + i; // 右端点
                if (r + i > n + 1) break;
                // cout << "[" << l << " " << r << ")" << endl;
                // cout << "[" <<  r << " " << r + i << ")" << endl;
                unsigned long long hash1 = a[r - 1] - a[l - 1] * p[i];
                unsigned long long hash2 = a[r + i - 1] - a[r - 1] * p[i];
                // cout << hash1 << endl;
                // cout << hash2 << endl;
                // cout << endl;
                if (hash1 == hash2) {
                    res[hash1] += 1;
                }
            }
        }
        return res.size();
    }
};