题面描述
给出两个串,从头开始匹配,如果在A串中找到一个B串就删去,然后再从头继续匹配,因为接上的地方可以会出现新的B串
求最后剩余的串
问题解决
看到这个问题,第一想到的就是 (KMP) 我们发现 (KMP) 能帮助我们快速匹配一个串
但是考虑要删除,这样删除串的方法很想栈的原理,所以考虑用栈来模拟
分别记下 (A)(主串) 中匹配时的 (j) 的值,方便在把后面的串删后继续匹配,然后每匹配到一个字母就加入栈,如果匹配到 (B) 了就从栈中删去
最后栈后留下的就是答案了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char a[maxn],b[maxn];
int len_a,len_b;
int kmp[maxn];
struct node{
char ch;
int km;
};
class stack{
private:
public:
node p[maxn];
int Top;
stack(){Top=0;}
node top(){return p[Top];}
void pop(int k=1){Top-=k;}
void push(node x){p[++Top]=x;}
}St;
int main(){
freopen("P4824.in","r",stdin);
freopen("P4824.out","w",stdout);
scanf("%s",a+1);
scanf("%s",b+1);len_a=strlen(a+1);len_b=strlen(b+1);
int j=0;
for(int i=2;i<=len_b;i++){
while(j&&b[j+1]!=b[i])j=kmp[j];
if(b[j+1]==b[i])j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=len_a;i++){
while(j&&b[j+1]!=a[i])j=kmp[j];
if(b[j+1]==a[i])j++;
if(j==len_b)St.pop(len_b-1);
else St.push((node){a[i],j});
j=St.top().km;
}
for(int i=1;i<=St.Top;i++){
putchar(St.p[i].ch);
}
return 0;
}