看着这一篇博客学会的，感谢大佬详细的教程： https://www.luogu.org/blog/lc-2018-Canton/solution-p5410
但是代码学的kuangbin巨巨的板子

代码: 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 4;
char s[maxn];
int Next[maxn],extend[maxn];
void pre_ex_kmp(char x[],int m)
{
	Next[0]=m;
	int j=0,k=1;
	while(j+1<m&&x[j]==x[j+1]) j++;
	Next[1]=j;
	for(int i=2;i<m;i++) {
		int p=Next[k]+k-1,L=Next[i-k];
		if(i+L<p+1) Next[i]=L;
		else {
			j=max(0,p-i+1);
			while(i+j<m&&x[i+j]==x[j]) j++;
			Next[i]=j;
			k=i;
		} 
	}
}
void ex_kmp(char x[],int m,char y[],int n)
{
	pre_ex_kmp(x,m);
	int j=0;
	while(j<n&&j<m&&x[j]==y[j]) j++;
	extend[0]=j;
	int k=0;
	for(int i=1;i<n;i++) {
		int p=extend[k]+k-1,L=Next[i-k];
		if(i+L<p+1) extend[i]=L;
		else {
			j=max(0,p-i+1);
			while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
			extend[i]=j;
			k=i;
		}
	}
}
int main()
{
	char s[maxn],t[maxn];
	scanf("%s%s",s,t);
	int m=strlen(t),n=strlen(s);
	ex_kmp(t,m,s,n);
	for(int i=0;i<m;i++) printf("%d ",Next[i]);
	printf("\n");
	for(int i=0;i<n;i++) printf("%d ",extend[i]);
	return 0;
}