我太菜了
今天才学会kmp
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<queue> 8 #include<map> 9 #include<vector> 10 #define ll long long 11 #define inf 2147483611 12 #define MAXN 1000100 13 #define MOD 1000000 14 using namespace std; 15 inline int read() 16 { 17 int x=0,f=1;char ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 char a[MAXN],b[MAXN]; 23 int n,m,j,nxt[MAXN]; 24 int main() 25 { 26 scanf("%s%s",a+1,b+1); 27 n=strlen(a+1),m=strlen(b+1); 28 for(int i=2;i<=m;i++) 29 { 30 while(j>0&&b[j+1]!=b[i]) j=nxt[j]; 31 if(b[j+1]==b[i]) j++; 32 nxt[i]=j; 33 } 34 j=0; 35 for(int i=1;i<=n;i++) 36 { 37 while(j>0&&b[j+1]!=a[i]) j=nxt[j]; 38 if(b[j+1]==a[i]) j++; 39 if(j==m) {printf("%d ",i-m+1);j=nxt[j];} 40 } 41 for(int i=1;i<=m;i++) 42 { 43 printf("%d ",nxt[i]); 44 } 45 }