用字符串哈希求解

既然学了字符串哈希，不妨回过头来把KMP重新做一下吧~

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 10, P = 131;


char s[N], t[N];  // s为匹配串，t为模式串
int n, m;         // m > n
ULL hs[N], ht[N], p[N];  // hs为s的哈希表，ht为t的哈希表

ULL sget(int l, int r)
{
    return hs[r] - hs[l - 1] * p[r - l + 1];
}

ULL tget(int l, int r)
{
    return ht[r] - ht[l - 1] * p[r - l + 1];
}

int main()
{
    cin >> n >> t + 1 >> m >> s + 1;

    // 预处理P的k次方 和 哈希表
    p[0] = 1;
    for (int i = 1; i <= m; i ++)
    {
        p[i] = p[i - 1] * P;
        hs[i] = hs[i - 1] * P + s[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        ht[i] = ht[i - 1] * P + t[i];
    }

    ULL thash = tget(1, n);  // 模式串的哈希值

    for (int i = 1; i + n - 1 <= m; i ++)
    {
        ULL shash = sget(i, i + n - 1);  // 与模式串长度相同的字串的哈希值
        if (thash == shash) cout << i - 1 << " ";  // 下标还原为从0开始
    }
}