滚动哈希是Rabin-Karp字符串匹配算法的核心机制，它通过预先计算模式串和文本串窗口的哈希值，快速判断两个子串是否可能相等，从而减少不必要的逐字符比对，提升匹配效率。在C++中实现该算法时，需要重点处理哈希值的计算、更新以及溢出问题。
滚动哈希的基本原理
滚动哈希的核心思想是，当文本串的匹配窗口向后滑动一位时，新的窗口哈希值可以通过上一个窗口的哈希值快速推导得到，不需要重新计算整个窗口的哈希。通常我们会选择一个基数base和一个大质数mod，将字符串看作base进制的数，对mod取模得到哈希值，避免数值过大溢出。
假设当前窗口的哈希值为hash_val，窗口长度为m，下一个字符为c，上一个窗口的第一个字符为old_c，那么新的哈希值计算逻辑为：
new_hash = (hash_val * base - old_c * pow_base + c) % mod
其中pow_base是base^(m-1)对mod取模的结果，需要预先计算好。
C++实现Rabin-Karp算法步骤
1. 预处理参数
首先需要确定基数base和模数mod，base通常选择256（覆盖所有ASCII字符），mod选择一个足够大的质数，减少哈希冲突的概率。同时计算base^(m-1) % mod的值，用于后续滚动更新哈希。
2. 计算模式串哈希
遍历模式串，按照滚动哈希的规则计算模式串的哈希值，作为后续比对的基准。
3. 计算文本串初始窗口哈希
取文本串前m个字符，计算初始窗口的哈希值，和模式串哈希值进行比对。
4. 滚动更新哈希并匹配
从文本串第m位开始，每次滑动窗口时更新哈希值，若哈希值相等，再逐字符比对确认是否真正匹配，避免哈希冲突导致的误判。
完整C++代码实现
以下是完整的Rabin-Karp字符串匹配C++实现代码：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 基数和模数，可根据需求调整
const int BASE = 256;
const int MOD = 1e9 + 7;
// 计算base的k次方对mod取模的结果
long long pow_mod(long long base, int k, int mod) {
long long res = 1;
while (k > 0) {
if (k % 2 == 1) {
res = (res * base) % mod;
}
base = (base * base) % mod;
k /= 2;
}
return res;
}
// Rabin-Karp字符串匹配函数，返回所有匹配起始下标
vector<int> rabin_karp(const string& text, const string& pattern) {
vector<int> res;
int n = text.size();
int m = pattern.size();
if (m == 0 || n < m) {
return res;
}
// 计算base^(m-1) % MOD
long long pow_base = pow_mod(BASE, m - 1, MOD);
// 计算模式串哈希
long long pattern_hash = 0;
for (int i = 0; i < m; i++) {
pattern_hash = (pattern_hash * BASE + pattern[i]) % MOD;
}
// 计算文本串初始窗口哈希
long long text_hash = 0;
for (int i = 0; i < m; i++) {
text_hash = (text_hash * BASE + text[i]) % MOD;
}
// 初始窗口比对
if (text_hash == pattern_hash) {
bool match = true;
for (int i = 0; i < m; i++) {
if (text[i] != pattern[i]) {
match = false;
break;
}
}
if (match) {
res.push_back(0);
}
}
// 滚动更新哈希并匹配
for (int i = m; i < n; i++) {
// 移除窗口第一个字符，加入新字符
text_hash = (text_hash - text[i - m] * pow_base) % MOD;
if (text_hash < 0) {
text_hash += MOD;
}
text_hash = (text_hash * BASE + text[i]) % MOD;
// 哈希相等时逐字符比对
if (text_hash == pattern_hash) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i - m + 1 + j] != pattern[j]) {
match = false;
break;
}
}
if (match) {
res.push_back(i - m + 1);
}
}
}
return res;
}
int main() {
string text = "abracadabra";
string pattern = "abra";
vector<int> matches = rabin_karp(text, pattern);
cout << "匹配到的起始下标：";
for (int idx : matches) {
cout << idx << " ";
}
cout << endl;
return 0;
}
算法复杂度分析
Rabin-Karp算法的时间复杂度分为两部分：
- 预处理阶段：计算模式串哈希和初始窗口哈希，时间复杂度为O(m)，m为模式串长度。
- 匹配阶段：每次滚动更新哈希的时间为O(1)，若出现哈希冲突需要逐字符比对，最坏情况下时间复杂度为O(nm)，但平均情况下哈希冲突概率极低，平均时间复杂度为O(n)，n为文本串长度。
该算法适合多模式串匹配的场景，只需要预先计算所有模式串的哈希值，就可以在一次文本串遍历中完成所有模式串的匹配，效率优势明显。
C++滚动哈希Rabin-Karp字符串匹配修改时间：2026-07-19 15:15:27