字符串哈希

简介

该算法通过把字符串变成一个 \(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]\) 的值。

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

例题：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();
    }
};