专栏文章

谈谈字符哈希

mmohay
算法·理论参与者 9已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@mioemmm7
此快照首次捕获于
2025/12/02 17:57
3 个月前
此快照最后确认于
2025/12/02 17:57
3 个月前
查看原文
哈希是一种映射，通过一丢丢计算得到的就叫哈希值。
通过对两个数的哈希值比较，如果哈希值相等视为两个数相等。
运用在字符串匹配问题上可大幅度降低时间复杂度，将逐个逐个字符比较的时间复杂度给“吃掉”，比较是否相同的时间复杂度从 O(n)O(n) 降为 O(1)O(1)。
  • Q：字符串不是数字,如何计算哈希值？
  • A：通常我们采用的是多项式 Hash 的方法：
f(s)=(∑i=1lsi×bl−i) mod Mf(s) = \left( \sum_{i=1}^{l} s_i \times b^{l-i} \right) \bmod M
bb 为某个基数，MM 为某个模数。
代码可以这样写：
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
解决办法也是比较简单，直接在加一个哈希函数。
双哈希，双重保障，被卡的概率大大减少。
{H1(S)=(S0⋅p1n−1+S1⋅p1n−2+⋯+Sn−1)mod  m1H2(S)=(S0⋅p2n−1+S1⋅p2n−2+⋯+Sn−1)mod  m2\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}
代码可参考下面的：
CPP
#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。
可以用前缀和的思想来优化。
为什么能用前缀优化呢？
我们的哈希公式是一个一个字符从头到尾来计算，对于字符串 ss，其长度为 ii 的前缀哈希值为：
fi(s)=∑k=1isk⋅bi−kf_i(s) = \sum_{k=1}^{i} s_k \cdot b^{i-k}
任意子串 sl→rs_{l \to r} 的哈希值可表示为：
f(sl→r)=∑k=lrsk⋅br−kf(s_{l \to r}) = \sum_{k=l}^{r} s_k \cdot b^{r-k}
通过数学变换可得：
f(sl→r)=fr(s)−fl−1(s)⋅br−l+1f(s_{l \to r}) = f_r(s) - f_{l-1}(s) \cdot b^{r-l+1}
代码如下：
CPP
#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

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

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...