字符串哈希CSP-S

💡 核心思想

字符串哈希是将字符串映射为一个整数的技巧。通常选择一个基数（如 131 或 13331）和一个大质数模数（如 10⁹+7），将字符串看作一个 p 进制数。通过预处理前缀哈希，可以在 O(1) 时间内比较任意两个子串是否相等。双哈希（两个不同模数）可以极大降低冲突概率。

🎯 直觉理解

想象你给每个字符串一个"身份证号"：把字符串当成一个特殊的数字，a=1, b=2, c=3... 然后按位加权求和，比如 "abc" = 1×131² + 2×131¹ + 3×131⁰。这样每个字符串都有唯一的数字表示，比较子串就像比较两个数字是否相等。

📝 算法流程

1. 选择基数 P（如 131）和模数 MOD（如 10⁹+7）
2. 预处理前缀哈希：H[i] = (H[i-1] × P + s[i]) % MOD
3. 预处理幂次：POW[i] = (POW[i-1] × P) % MOD
4. 子串 [l, r] 的哈希值：hash = (H[r] - H[l-1] × POW[r-l+1] % MOD + MOD) % MOD
5. 两个子串哈希值相同，则认为子串相等（概率意义上）

$$H[i] = (H[i-1] \times P + s_i) \bmod MOD$$

$$hash(l, r) = (H[r] - H[l-1] \times P^{r-l+1}) \bmod MOD$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

typedef long long ll;
const int P = 131;
const ll MOD = 1e9 + 7;

// 单哈希
struct StringHash {
    vector h, p;
    StringHash(const string& s) {
        int n = s.size();
        h.resize(n + 1);
        p.resize(n + 1);
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = (h[i-1] * P + s[i-1]) % MOD;
            p[i] = (p[i-1] * P) % MOD;
        }
    }
    // 获取子串 [l, r] 的哈希值（1-based，闭区间）
    ll get(int l, int r) {
        ll res = (h[r] - h[l-1] * p[r-l+1] % MOD + MOD) % MOD;
        return res;
    }
};

// 双哈希（更安全）
struct DoubleHash {
    vector h1, h2, p1, p2;
    const ll P2 = 13331, MOD2 = 1e9 + 9;
    DoubleHash(const string& s) {
        int n = s.size();
        h1.resize(n+1); h2.resize(n+1); p1.resize(n+1); p2.resize(n+1);
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= n; i++) {
            h1[i] = (h1[i-1] * P + s[i-1]) % MOD;
            h2[i] = (h2[i-1] * P2 + s[i-1]) % MOD2;
            p1[i] = (p1[i-1] * P) % MOD;
            p2[i] = (p2[i-1] * P2) % MOD2;
        }
    }
    pair get(int l, int r) {
        ll a = (h1[r] - h1[l-1] * p1[r-l+1] % MOD + MOD) % MOD;
        ll b = (h2[r] - h2[l-1] * p2[r-l+1] % MOD2 + MOD2) % MOD2;
        return {a, b};
    }
};

int main() {
    string s = "ababcab";
    StringHash sh(s);
    
    // 比较子串 "ab" 和 "ab"
    cout << (sh.get(1, 2) == sh.get(4, 5) ? "Equal" : "Not Equal") << endl;
    cout << (sh.get(1, 2) == sh.get(3, 4) ? "Equal" : "Not Equal") << endl;
    
    // 找模式串 "abc" 在主串中的位置
    string pat = "abc";
    StringHash ph(pat);
    ll target = ph.get(1, pat.size());
    for (int i = 1; i + pat.size() - 1 <= s.size(); i++)
        if (sh.get(i, i + pat.size() - 1) == target)
            cout << "Found at " << i << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目