并没有搞懂于是先把模板发上来吧
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 int l1,l2,next[100001],extend[100001]; 7 char s[100001],t[100001]; 8 void getnext(){ 9 int a=0,p; 10 next[0]=l2; 11 for(int i=1,j=-1;i<l2;i++,j--){ 12 if(j<0||i+next[i-a]>=p){ 13 if(j<0){ 14 p=i; 15 j=0; 16 } 17 while(p<l2&&t[p]==t[j]){ 18 p++; 19 j++; 20 } 21 next[i]=j; 22 a=i; 23 }else next[i]=next[i-a]; 24 } 25 } 26 void getex(){ 27 int a=0,p; 28 for(int i=0,j=-1;i<l1;i++,j--){ 29 if(j<0||i+next[i-a]>=p){ 30 if(j<0){ 31 p=i; 32 j=0; 33 } 34 while(p<l1&&s[p]==t[j]){ 35 p++; 36 j++; 37 } 38 extend[i]=j; 39 a=i; 40 }else extend[i]=next[i-a]; 41 } 42 } 43 int main(){ 44 memset(next,0,sizeof(next)); 45 scanf("%s%s",s,t); 46 l1=strlen(s); 47 l2=strlen(t); 48 getnext(); 49 getex(); 50 for(int i=0;i<l2;i++){ 51 printf("%d ",next[i]); 52 } 53 printf(" "); 54 for(int i=0;i<l1;i++){ 55 printf("%d ",extend[i]); 56 } 57 return 0; 58 }