KMP

zhuyuhao1123 · 2025-10-21 15:57:05 · 算法·理论

#include<bits/stdc++.h>
using namespace std;
char a[1000001];
int p[1000001],n;
void prepare()
{
    p[1]=0;
    int j=0;
    for(int i=1;i<n;++i)
    {
        while(j>0&&a[j+1]!=a[i+1]) j=p[j];
        if(a[j+1]==a[i+1]) j++;
        p[i+1]=j;
    }
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    prepare();
    return 0;
}