分析:..每次直接加入栈，然后用kmp来匹配就可以了。。然而我第一次kmp的时候把第二个写成第一个串WA了无数次。。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N=1e6+1e3+5; char s1[N],stack[N],s2[N]; int next[N],n,m; int a[N],top; int main() { scanf("%s%s",s1+1,s2+1); n=strlen(s1+1); m=strlen(s2+1); int j=0; fo(i,2,m) { while (j&&s2[j+1]!=s2[i])j=next[j]; if (s2[j+1]==s2[i])j++; next[i]=j; } top=0; fo(i,1,n) { stack[++top]=s1[i]; int j=a[top-1]; while (j&&s2[j+1]!=stack[top])j=next[j]; if (s2[j+1]==stack[top])j++; a[top]=j; if (a[top]==m)top-=m; } stack[top+1]=0; puts(stack+1); return 0; }