给出一个母串和一个模式串，当前一个一个地将母串插入到一个字符串中，如果在插入的过程中，当前字符串以模式串为后缀，则将这个模式串从字符串中删除，然后继续插入
求出最后得到的字符串
KMP，先求模式串的p数组
然后直接一个一个地插入母串，实时更新q数组就行了（q[i]表示字符串第i位的后缀与模式串前缀的最大匹配长度）
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; char A[1100000],B[1100000]; char st[1100000]; int p[1100000],q[1100000]; int main() { scanf("%s%s",A+1,B+1); int len1=strlen(A+1),len2=strlen(B+1); p[1]=0; for(int i=2;i<=len2;i++) { int j=p[i-1]; while(j!=0&&B[j+1]!=B[i]) j=p[j]; if(B[j+1]==B[i]) p[i]=j+1; } int tp=0; for(int i=1;i<=len1;i++) { st[++tp]=A[i]; int j=q[tp-1]; while(j!=0&&B[j+1]!=st[tp]) j=p[j]; if(B[j+1]==st[tp]) q[tp]=j+1; else q[tp]=0; if(q[tp]==len2) for(int k=1;k<=len2;k++) tp--; } for(int i=1;i<=tp;i++) printf("%c",st[i]); printf("\n"); return 0; }
BZOJ3942: [Usaco2015 Feb]Censoring
原文：https://www.cnblogs.com/Never-mind/p/9951644.html