c++使用hash算法实现字符串匹配

C++中使用hash算法实现字符串匹配，可以采用Rabin-Karp算法。

该算法的基本思想是：将模式串和文本串都看作是一个进制为d的数，通过哈希函数将它们映射为一个整数。由于哈希函数的映射是唯一的，因此只要哈希值相等，就说明模式串和文本串可能相等。因此在比较之前，先比较它们的哈希值，若相等则说明它们可能相等，再逐个比较字符。

具体实现如下：

#include <iostream>
#include <string>

using namespace std;

const int BASE = 131; // 哈希函数的基数
const int MOD = 1e9 + 7; // 哈希函数的模数

int Hash(string s) // 哈希函数
{
    int res = 0;
    for (int i = 0; i < s.length(); i++) {
        res = ((long long)res * BASE + s[i]) % MOD;
    }
    return res;
}

int main()
{
    string text, pattern;
    cin >> text >> pattern;

    int patternHash = Hash(pattern); // 计算模式串的哈希值

    int textHash = 0;
    int t = 1;
    for (int i = 0; i < pattern.length(); i++) {
        textHash = ((long long)textHash * BASE + text[i]) % MOD; // 计算初始文本串的哈希值
        t = ((long long)t * BASE) % MOD;
    }

    for (int i = 0; i + pattern.length() <= text.length(); i++) {
        if (textHash == patternHash && text.substr(i, pattern.length()) == pattern) {
            cout << "Pattern found at index " << i << endl;
        }
        if (i + pattern.length() < text.length()) {
            textHash = ((long long)textHash * BASE - (long long)text[i] * t % MOD + MOD) % MOD; // 更新文本串的哈希值
            textHash = ((long long)textHash + text[i + pattern.length()]) % MOD;
        }
    }

    return 0;
}

该算法的时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。