题解
手写栈存放已经匹配过的位置和每个位置匹配的进度,每次匹配成功就回溯,相当于删除子串
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int con[1000006],pre[1000006]={0},st[1000006]={0};
void solve()
{
string s1,s2;
cin>>s1>>s2;
int n=s1.size();
int len=s2.size();
s1=' '+s1;
s2=' '+s2;
int it=0;
for(int i=2;s2[i];i++)
{
while(it&&s2[it+1]!=s2[i]) it=pre[it];
if(s2[it+1]==s2[i]) it++;
pre[i]=it;
}
//for(int i=1;i<=len;i++) cout<<pre[i]<<' ';cout<<'\n';
int top=1;
it=0;
for(int i=1;s1[i];i++)
{
while(it&&s2[it+1]!=s1[i]) it=pre[it];
if(s2[it+1]==s1[i]) it++;
//printf("top:%d it:%d\n",top,it);
con[i]=it;
if(con[i]==len)
{
top-=len;
it=con[st[top]];
top++;
}
else st[top++]=i;
}
for(int i=1;i<top;i++) cout<<s1[st[i]];
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
标签:pre,int,s2,s1,while,Censoring,1000006,USACO15FEB,P4824
From: https://www.cnblogs.com/pure4knowledge/p/18315151