kuangbin专题十六：KMP & 扩展KMP & Manacher

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int maxm = 1e4 + 5;
const int maxn = 1e6 + 5;
int T, n, m;

int a[maxn], b[maxm];
int Next[maxm];

void genNext(){
    Next[0] = -1;
    int j = -1;
    for(int i = 1; i < m; i++){
        while(j != -1 && b[i] != b[j+1]) j = Next[j];
        if(b[i] == b[j+1]) j++;
        Next[i] = j;
    }
}

int kmp(){
    int j = -1;
    for(int i = 0; i < n; i++){
        while(j != -1 && a[i] != b[j+1]) j = Next[j];
        if(a[i] == b[j+1]) j++;

        if(j == m-1)
            return i - m + 2;
    }
    return -1;
}

int main(){
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++) scanf("%d", a+i);
        for(int i = 0; i < m; i++) scanf("%d", b+i);

        genNext();
        printf("%d\n", kmp());
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;

char W[maxm], T[maxn];
int Next[maxm];

int Tn, n, m;

void genNext() {
    Next[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++){
        while(j != -1 && W[i] != W[j+1]) j = Next[j];
        if(W[i] == W[j+1]) j++;
        Next[i] = j;
    }
}

int kmp(){
    int j = -1, res = 0;
    for(int i = 0; i < n; i++){
        while(j != -1 && T[i] != W[j+1]) j = Next[j];
        if(T[i] == W[j+1]) j++;

        if (j == m-1)
            res++, j = Next[j];
    }
    return res;
}

int main(){
    scanf("%d", &Tn);
    while(Tn--){
        scanf("%s", W);
        scanf("%s", T);
        m = strlen(W), n = strlen(T);

        genNext();
        printf("%d\n", kmp());
    }
    return 0;
}