P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N=1e6+100;
int n=0,m;
char s1[N];
char s2[N];
int Next[N];
int main()
{
    scanf("%s",s1+1);//输入字符串，（从下标为1的位置开始输入）
    scanf("%s",s2+1);//模式串，（从下标为1的位置开始输入）
    int lens1=strlen(s1+1);
    int lens2=strlen(s2+1);
    for(int i=2,j=0;i<=lens2;i++)//求next数组
    {
        while(j&&s2[i]!=s2[j+1])
            j=Next[j];
        if(s2[i]==s2[j+1])
            j++;
        Next[i]=j;
    }
    for(int i=1,j=0;i<=lens1;i++)
    {
        while(j&&s1[i]!=s2[j+1])
            j=Next[j];
        if(s1[i]==s2[j+1])
            j++;
        if(j==lens2)
        {
            printf("%d\n",i-lens2+1);//输出匹配的位置
            j=Next[j];
        }
    }
    for(int i=1;i<=lens2;i++)//输出next数组
        printf("%d ",Next[i]);
    return 0;
}