在c++里用字符串哈希写KMP

KMP算法是一种用于字符串匹配的算法，其中最关键的部分是构建next数组，用于指导模式串的匹配过程。在构建next数组的时候，可以使用字符串哈希的思想，将模式串的前缀和后缀进行哈希处理，然后进行比较，从而得出next数组。

具体实现如下：

#include <stdio.h>
#include <string.h>

#define ll long long

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

char s[N], t[N];
int n, m;
ll h[N], p[N], ht[N], pt[N], nxt[N];

void init() {
    p[0] = pt[0] = 1;
    for(int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    for(int i = 1; i <= m; ++i) {
        ht[i] = ht[i - 1] * P + t[i];
        pt[i] = pt[i - 1] * P;
    }
}

int check(int len) {
    for(int i = 1; i + len - 1 <= m; ++i) {
        ll h1 = ht[i + len - 1] - ht[i - 1] * pt[len];
        ll h2 = h[len];
        if(h1 == h2) return i;
    }
    return 0;
}

void getnxt() {
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; ++i) {
        while(j && t[j + 1] != t[i]) j = nxt[j];
        if(t[j + 1] == t[i]) ++j;
        nxt[i] = j;
    }
}

int main() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    init();
    getnxt();
    int j = 0;
    for(int i = 1; i <= n; ++i) {
        while(j && t[j + 1] != s[i]) j = nxt[j];
        if(t[j + 1] == s[i]) ++j;
        if(j == m) {
            printf("%d\n", i - m + 1);
            j = nxt[j];
        }
    }
    return 0;
}

其中，h[i]表示s的前i个字符的哈希值，ht[i]表示t的前i个字符的哈希值。p[i]和pt[i]分别表示P的i次方。check函数用于检查长度为len的模式串是否在t中出现过，并返回第一次出现的位置。getnxt函数用于计算next数组。在主函数中，使用KMP算法进行匹配，当j等于m时，说明匹配成功，输出匹配的起始位置，并更新j为nxt[j]，继续匹配。