Rabin-Karp字符串匹配算法详解（C++语言RK算法实现指南）

RK算法的优势与适用场景

• 适合在大文本中查找多个模式串（如 plagiarism detection）
• 平均时间复杂度为 O(n + m)，其中 n 是文本长度，m 是模式串长度
• 预处理简单，易于实现

C++实现RK算法步骤

我们将使用一个简单的滚动哈希（rolling hash）策略，基于多项式哈希（Polynomial Rolling Hash）来实现RK算法。

1. 定义常量和辅助函数

我们选择一个较大的质数作为模数（例如 101），并使用基数（base）为 256（对应ASCII字符集）。

#include <iostream>#include <string>#include <vector>using namespace std;const int prime = 101; // 一个较小的质数，用于取模const int base = 256;  // ASCII 字符总数

2. 计算模式串的哈希值

我们需要一个函数来计算任意字符串的哈希值：

long long calculateHash(const string& str, int len) {    long long hash = 0;    for (int i = 0; i < len; ++i) {        hash = (hash * base + str[i]) % prime;    }    return hash;}

3. 实现滚动哈希更新

当窗口向右滑动一位时，我们可以利用前一个哈希值快速计算新窗口的哈希值：

long long recalculateHash(const string& str, int oldIndex, int newIndex,                           long long oldHash, int patternLen) {    long long newHash = oldHash - str[oldIndex] * pow(base, patternLen - 1);    newHash = (newHash * base + str[newIndex]) % prime;    if (newHash < 0) newHash += prime; // 处理负数    return newHash;}

注意：上面的 pow(base, patternLen - 1) 可能效率不高，实际项目中建议预先计算该值。

4. 主匹配函数

整合上述逻辑，完成完整的RK算法实现：

vector<int> rabinKarpSearch(const string& text, const string& pattern) {    vector<int> matches;    int n = text.length();    int m = pattern.length();        if (m > n) return matches;        // 预计算 base^(m-1) % prime    long long h = 1;    for (int i = 0; i < m - 1; ++i) {        h = (h * base) % prime;    }        long long patternHash = calculateHash(pattern, m);    long long textHash = calculateHash(text, m);        for (int i = 0; i <= n - m; ++i) {        // 如果哈希值匹配，再逐字符验证        if (patternHash == textHash) {            bool match = true;            for (int j = 0; j < m; ++j) {                if (text[i + j] != pattern[j]) {                    match = false;                    break;                }            }            if (match) {                matches.push_back(i);            }        }                // 滚动到下一个窗口（如果不是最后一个）        if (i < n - m) {            textHash = (base * (textHash - text[i] * h) + text[i + m]) % prime;            if (textHash < 0) textHash += prime;        }    }        return matches;}

5. 完整测试代码

int main() {    string text = "ABABCABABA";    string pattern = "ABA";        vector<int> result = rabinKarpSearch(text, pattern);        cout << "Pattern found at indices: ";    for (int idx : result) {        cout << idx << " ";    }    cout << endl;        return 0;}

常见问题与优化建议

- 哈希冲突：虽然概率低，但可能发生。因此必须进行二次验证。

- 大数溢出：在 C++ 中使用 long long 并配合取模可有效避免。

- 性能优化：对于超长文本，可考虑使用更大的质数（如 10^9+7）或双哈希策略提升准确性。

总结

通过本教程，你已经掌握了如何用C++语言实现RK算法进行高效的字符串匹配。RK算法（Rabin-Karp算法）以其简洁性和在多模式匹配中的优势，成为字符串处理领域的重要工具。希望你能将所学应用到实际项目中，比如文本搜索、生物信息学序列比对等场景。

关键词回顾：RK算法、C++字符串匹配、Rabin-Karp算法、C++实现RK算法。