洛谷P4824 [USACO15FEB] Censoring S 题解
题目链接:P4824 [USACO15FEB] Censoring S
题意:给出字符串 $t$ 和 $s$ ,删除在 $t$ 中第一次出现的子串 $s$ ,并重复这个过程(在产生的新串 $t’$ 上继续删除操作),求最后的结果
匹配问题可以用KMP来解决
怎么处理删除操作呢?
可以观察下样例
注意到删除子串后,在删除的子段后继续匹配可能需要该子段前的已经算出(显然)的匹配值
那么我们可以用两个栈分别维护KMP的匹配值和答案
在每次删除后我们只要让top-=m
即可,其中m
为 $s$ 的长度
时间复杂度 $O(|t|+|s|)$
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e6+5)
int n,m,fail[MAXN],top,stk[MAXN];
char t[MAXN],s[MAXN],ans[MAXN];
signed main()
{
scanf("%s\n%s\n",t+1,s+1);
n=strlen(t+1);m=strlen(s+1);
for(int i=2,j=0; i<=m; i++)
{
while(j&&s[i]!=s[j+1])j=fail[j];
if(s[i]==s[j+1])++j;
fail[i]=j;
}
for(int i=1,j=0; i<=n; i++)
{
while(j&&t[i]!=s[j+1])j=fail[j];
if(t[i]==s[j+1])++j;
stk[++top]=j;
ans[top]=t[i];
if(j==m)top-=m,j=stk[top];
}
ans[top+1]='\0'; // 不要忘了这个哦!
printf("%s",ans+1);
return 0;
}
当然这个题还有个加强版
做法类似,只不过变成多模式串匹配了而已,题解。