字符串hash

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define js                       \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr)
typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
/*
根据经验
p进制,选p=131或13331;
mod Q,选Q=2^64;
则冲突概率很低
*/
// 这里采用 高-->低位 的顺序hash

const int N = 1e6 + 5, P = 131;
ull charshash[N], p[N], psh[N / 10 + 5];
char pstr[N / 10 + 5], s[N];

ull get(itn l, int r)
{
    return charshash[r] - charshash[l - 1] * p[r - l + 1];
}

int main()
{
    js;
    int n, m;
    cin >> n >> pstr >> m >> s;

    p[0] = 1;
    for (int i = 1; i <= m; i++) {
        charshash[i] = charshash[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    for (int i = 1; i <= n; i++)
        psh[i] = psh[i - 1] * P + pstr[i];

    ull thsp = psh[n];
    for (itn i = 1; i + n - 1 <= m; i++) {
        if (get(i, i + n - 1) == thsp)
            cout << i - 1 << ' ';
    }

    return 0;
}