谈谈字符哈希

· · 算法·理论

哈希是一种映射，通过一丢丢计算得到的就叫哈希值。

通过对两个数的哈希值比较，如果哈希值相等视为两个数相等。

运用在字符串匹配问题上可大幅度降低时间复杂度，将逐个逐个字符比较的时间复杂度给“吃掉”，比较是否相同的时间复杂度从 O(n) 降为 O(1)。

f(s) = \left( \sum_{i=1}^{l} s_i \times b^{l-i} \right) \bmod M 代码可以这样写： ```cpp ull get_hash(string s) {//用于输入时预处理 int len = s.size(); ull ans = 0; for (int i = 0; i < len; i++) ans = (ans * b + (ull)s[i]) % M; return ans; } ``` 可是这样做很有可能被卡，这里不展开讲。 [详细见 oi-wiki 卡 Hash](https://oi-wiki.org/string/hash/#%E5%8D%A1%E5%A4%A7%E6%A8%A1%E6%95%B0-hash) 解决办法也是比较简单，直接在加一个哈希函数。 双哈希，双重保障，被卡的概率大大减少。 $\begin{cases} H_1(S) = (S_0 \cdot p_1^{n-1} + S_1 \cdot p_1^{n-2} + \cdots + S_{n-1}) \mod m_1 \\ H_2(S) = (S_0 \cdot p_2^{n-1} + S_1 \cdot p_2^{n-2} + \cdots + S_{n-1}) \mod m_2 \end{cases}

代码可参考下面的：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

// 双哈希类，使用两种不同的哈希函数来减少冲突概率
class DH {
    vector<ull> h1, h2; // 存储两种哈希的前缀值
    vector<ull> p1, p2;  // 存储基数的幂次，用于快速计算子串哈希
    const ull b1 = 131, b2 = 13331; // 两种不同的基数
    const ull m1 = 1e9+7, m2 = 998244353; // 两种不同的模数

public:
    // 初始化哈希预处理数组
    void init(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] * b1 + s[i-1]) % m1;
            // 计算第二种哈希的前缀值
            h2[i] = (h2[i-1] * b2 + s[i-1]) % m2;
            // 计算基数的i次幂
            p1[i] = (p1[i-1] * b1) % m1;
            p2[i] = (p2[i-1] * b2) % m2;
        }
    }

    // 获取子串s[l..r)的双哈希值
    pair<ull, ull> get(int l, int r) {
        // 计算第一种哈希的子串哈希值
        ull v1 = (h1[r] - h1[l] * p1[r-l] % m1 + m1) % m1;
        // 计算第二种哈希的子串哈希值
        ull v2 = (h2[r] - h2[l] * p2[r-l] % m2 + m2) % m2;
        return {v1, v2};
    }
};

// 在字符串s中查找模式串p的所有出现位置
vector<int> find(string s, string p) {
    DH ds, dp; // 创建两个双哈希对象，分别用于s和p

    // 预处理两个字符串的哈希
    ds.init(s);
    dp.init(p);

    // 获取模式串p的完整哈希值
    auto t = dp.get(0, p.size());

    vector<int> res; // 存储所有匹配位置的起始索引

    // 遍历s中所有可能的起始位置
    for(int i = 0; i <= s.size() - p.size(); i++) {
        // 比较s的子串和p的哈希值
        if(ds.get(i, i + p.size()) == t) {
            res.push_back(i); // 如果哈希匹配，记录位置
        }
    }
    return res;
}

前缀优化

如果题目要多次求子串，前面的代码还是不够看，还是会 TLE。

可以用前缀和的思想来优化。

为什么能用前缀优化呢？

我们的哈希公式是一个一个字符从头到尾来计算，对于字符串 s，其长度为 i 的前缀哈希值为：

f_i(s) = \sum_{k=1}^{i} s_k \cdot b^{i-k}

任意子串 s_{l \to r} 的哈希值可表示为：

f(s_{l \to r}) = \sum_{k=l}^{r} s_k \cdot b^{r-k}

通过数学变换可得：

f(s_{l \to r}) = f_r(s) - f_{l-1}(s) \cdot b^{r-l+1}

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

// 双哈希类，使用两种不同的哈希函数来减少冲突概率
class DoubleHash {
    vector<ull> h1, h2; // 存储两种哈希的前缀值
    vector<ull> p1, p2;  // 存储基数的幂次，用于快速计算子串哈希
    const ull b1 = 131, b2 = 13331; // 两种不同的基数
    const ull m1 = 1e9+7, m2 = 998244353; // 两种不同的模数
    int n; // 字符串长度

public:
    // 构造函数，初始化时直接预处理哈希
    DoubleHash(const string& s) {
        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] * b1 + s[i-1]) % m1;
            // 计算第二种哈希的前缀值
            h2[i] = (h2[i-1] * b2 + s[i-1]) % m2;
            // 预计算基数的幂次（避免重复计算）
            p1[i] = (p1[i-1] * b1) % m1;
            p2[i] = (p2[i-1] * b2) % m2;
        }
    }

    // 获取子串s[l..r)的双哈希值（带边界检查）
    pair<ull, ull> getHash(int l, int r) const {
        // 边界检查（前缀优化）
        if(l < 0 || r > n || l >= r) return {0, 0};

        // 计算第一种哈希的子串哈希值（使用预计算的幂次优化）
        ull v1 = (h1[r] - h1[l] * p1[r-l] % m1 + m1) % m1;
        // 计算第二种哈希的子串哈希值
        ull v2 = (h2[r] - h2[l] * p2[r-l] % m2 + m2) % m2;
        return {v1, v2};
    }

    // 获取字符串长度
    int size() const { return n; }
};

// 在字符串s中查找模式串p的所有出现位置（带前缀优化）
vector<int> findPattern(const string& s, const string& p) {
    // 边界条件检查（前缀优化）
    if(p.empty()) return {};
    if(s.size() < p.size()) return {};

    // 使用构造函数初始化（避免额外的init调用）
    DoubleHash ds(s), dp(p);

    // 获取模式串p的完整哈希值
    auto targetHash = dp.getHash(0, p.size());

    vector<int> res; // 存储所有匹配位置的起始索引
    res.reserve(s.size() / p.size()); // 预分配空间（前缀优化）

    // 遍历s中所有可能的起始位置
    int patternLen = p.size();
    for(int i = 0; i <= s.size() - patternLen; i++) {
        // 比较s的子串和p的哈希值
        if(ds.getHash(i, i + patternLen) == targetHash) {
            res.push_back(i); // 如果哈希匹配，记录位置
        }
    }
    return res;
}

// 示例
int main() {
    string text = "ababcabcabababd";
    string pattern = "ababd";

    auto positions = findPattern(text, pattern);

    cout << "Pattern found at positions: ";
    for(int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;

    return 0;
}

通过前缀我们能更好的解决字符串匹配问题。

THE END

我第一篇文章，纪念我的夏令营。