题意很简单，感觉这道题是陈题额。。
就是给两个字符串，A和B，把B中包含A的字符串都递归删除。
很明显的KMP了。。这题比赛的时候我推了很久。。因为字符串是弱项没有专门刷过。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1000000*5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
char strs[MAXN],tmp[MAXN],ans[MAXN];
int pre[MAXN],next[MAXN];
void InitP(char *B){
next[0]=next[1]=0;
for(int i=2,j=0;B[i];++i){
while(j>0&&B[j]!=B[i-1])j=next[j];
if(B[j]==B[i-1])++j;
next[i]=j;
}
}
int main()
{
while(~scanf(" %s %s",tmp,strs)){
InitP(tmp);
int len=strlen(strs);
int len1=strlen(tmp);
for(int i=0,j=0,k=0;i<len;i++,k++){
ans[k]=strs[i];
while(j>0&&strs[i]!=tmp[j])j=next[j];
if(strs[i]==tmp[j])++j;
if(j==len1){
k-=len1;
j=pre[k];
}
ans[k+1]=0;
pre[k]=j;
}
puts(ans);
}
return 0;
}
|
