c++中如何实现Rabin-Karp算法_c++ Rabin-Karp算法实现方法-C++-PHP中文网

c++中如何实现Rabin-Karp算法_c++ Rabin-Karp算法实现方法

穿越時空

发布： 2025-10-09 16:03:01

原创

234人浏览过

Rabin-Karp算法通过滚动哈希快速匹配字符串，先计算模式串与主串子串的哈希值，哈希相等时再逐字符验证；C++实现中选用合适进制和模数，利用滚动哈希公式在O(1)时间更新哈希值，减少比较次数；核心步骤包括预计算h=d^(m-1)%q、初始哈希值及滑动窗口中哈希更新，若哈希匹配则进行字符级比对；为降低冲突可选大质数模数或双哈希优化，平均时间复杂度O(n+m)，适用于多模式或大数据场景。

c++中如何实现rabin-karp算法_c++ rabin-karp算法实现方法

Rabin-Karp算法是一种字符串查找算法，利用哈希值快速匹配模式串与主串的子串。在C++中实现该算法，关键在于高效计算哈希值并处理哈希冲突。下面介绍具体实现方法。

基本思路

Rabin-Karp算法通过计算模式串和主串中每个等长子串的哈希值进行比较。只有当哈希值相等时，才逐字符验证是否真正匹配，从而减少不必要的比较。

核心步骤包括：

选择一个合适的进制数（如256）和模数（避免整数溢出）
预计算模式串的哈希值
使用滚动哈希技术计算主串中每个子串的哈希值
比较哈希值，相等时进行字符级比对

滚动哈希的实现

滚动哈希允许我们在O(1)时间内更新当前子串的哈希值。假设主串长度为n，模式串长度为m，则第i个子串的哈希值可以通过第i-1个子串的哈希值得到。

立即学习“C++免费学习笔记（深入）”；

公式如下：

千图设计室AI海报

千图网旗下的智能海报在线设计平台

172

查看详情

hash(i) = (d * (hash(i-1) - text[i-1] * h) + text[i+m-1]) % q

其中：

d是字符集大小（如ASCII用256）
q是模数（常用大质数，如101或更优的1e9+7）
h = d^(m-1) % q

C++代码实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;
<p>void rabinKarp(const string& text, const string& pattern, int d = 256, int q = 101) {
int n = text.length();
int m = pattern.length();</p><pre class='brush:php;toolbar:false;'>if (m > n) return;

// 预计算 h = d^(m-1) % q
int h = 1;
for (int i = 0; i < m - 1; i++)
    h = (h * d) % q;

// 计算模式串和第一个子串的哈希值
int pHash = 0, tHash = 0;
for (int i = 0; i < m; i++) {
    pHash = (d * pHash + pattern[i]) % q;
    tHash = (d * tHash + text[i]) % q;
}

// 滑动窗口匹配
for (int i = 0; i <= n - m; i++) {
    if (pHash == tHash) {
        // 哈希匹配，检查字符是否一致
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match)
            cout << "Pattern found at index " << i << endl;
    }

    // 更新主串中下一个子串的哈希值
    if (i < n - m) {
        tHash = (d * (tHash - text[i] * h) + text[i + m]) % q;
        if (tHash < 0) tHash += q; // 处理负数
    }
}

登录后复制

}

// 使用示例 int main() { string text = "ABABCABABCD"; string pattern = "ABABC"; rabinKarp(text, pattern); return 0; }