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

RK算法的基本步骤

1. 为模式串计算一个哈希值。
2. 为文本串中每个与模式串等长的子串计算哈希值。
3. 当两个哈希值相等时，再逐字符验证是否真正匹配（防止哈希冲突）。
4. 使用滚动哈希技术高效更新子串的哈希值。

C++实现RK算法

下面是一个完整的C++实现RK算法的示例代码。我们将使用一个简单的多项式滚动哈希，并选择一个大质数作为模数以减少冲突。

#include <iostream>#include <string>#include <vector>using namespace std;// 计算模式串的哈希值class RabinKarp {private:    const int prime = 101; // 选择一个质数作为基数    const long long mod = 1000000007; // 大质数模数public:    // 计算字符串的哈希值    long long calculateHash(const string& str) {        long long hash = 0;        for (char c : str) {            hash = (hash * prime + c) % mod;        }        return hash;    }    // 滚动哈希：从旧哈希值计算新哈希值    long long rollingHash(long long oldHash, char oldChar, char newChar, long long highestPow) {        long long newHash = (oldHash - (oldChar * highestPow) % mod + mod) % mod;        newHash = (newHash * prime + newChar) % mod;        return newHash;    }    // RK算法主函数    vector<int> search(const string& text, const string& pattern) {        vector<int> matches;        int n = text.length();        int m = pattern.length();        if (m > n) return matches;        // 预计算最高次幂：prime^(m-1) % mod        long long highestPow = 1;        for (int i = 0; i < m - 1; ++i) {            highestPow = (highestPow * prime) % mod;        }        // 计算模式串和文本首子串的哈希        long long patternHash = calculateHash(pattern);        long long textHash = calculateHash(text.substr(0, 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 = rollingHash(textHash, text[i], text[i + m], highestPow);            }        }        return matches;    }};// 测试函数int main() {    string text = "ABABCABABA";    string pattern = "ABABA";    RabinKarp rk;    vector<int> result = rk.search(text, pattern);    cout << "匹配位置: ";    for (int pos : result) {        cout << pos << " ";    }    cout << endl;    return 0;}

代码解析

上述代码实现了完整的RK算法：

• calculateHash：计算任意字符串的哈希值。
• rollingHash：利用前一个子串的哈希值快速计算下一个子串的哈希值。
• search：主匹配函数，返回所有匹配起始位置。

时间复杂度分析

在平均情况下，RK算法的时间复杂度为 O(n + m)，其中 n 是文本长度，m 是模式串长度。最坏情况（如大量哈希冲突）下退化为 O(nm)，但通过合理选择哈希函数和模数，可极大降低冲突概率。

总结

通过本教程，你已经学会了如何用C++语言实现RK算法进行高效的字符串匹配。无论你是准备面试，还是开发实际项目，掌握这一经典算法都将大有裨益。记住，理解滚动哈希的核心思想是掌握RK算法的关键！

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