Bzoj 3942: [Usaco2015 Feb]Censoring(kmp)
3942: [Usaco2015 Feb]Censoring
Description
Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).
FJ has taken all of the text from the magazine to create the string S of length at most 10^6 characters. From this, he would like to remove occurrences of a substring T to censor the inappropriate content. To do this, Farmer John finds the first occurrence of T in S and deletes it. He then repeats the process again, deleting the first occurrence of T again, continuing until there are no more occurrences of T in S. Note that the deletion of one occurrence might create a new occurrence of T that didn’t exist before.
Please help FJ determine the final contents of S after censoring is complete
有一个S串和一个T串,长度均小于1,000,000,设当前串为U串,然后从前往后枚举S串一个字符一个字符往U串里添加,若U串后缀为T,则去掉这个后缀继续流程。
Input
The first line will contain S. The second line will contain T. The length of T will be at most that of S, and all characters of S and T will be lower-case alphabet characters (in the range a..z).
Output
The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.
Sample Input
whatthemomooofun
moo
Sample Output
whatthefun
HINT
Source
Silver
/*
kmp+栈模拟.
先将t串自匹配.
然后将s与t串匹配.
又是fail数组的套路题orz.
*/
#include<cstring>
#include<cstdio>
#define MAXN 1000001
using namespace std;
int l1,l2,top,next[MAXN],fail[MAXN];
char s1[MAXN],s2[MAXN],ans[MAXN];
void slove()
{
int p;
for(int i=2;i<=l1;i++)
{
p=next[i-1];
while(p&&s2[i]!=s2[p+1]) p=next[p];
if(s2[i]==s2[p+1]) p++;
next[i]=p;
}
}
void kmp()
{
int p;
for(int i=1;i<=l1;i++)
{
ans[++top]=s1[i];
p=fail[top-1];
while(p&&ans[top]!=s2[p+1]) p=next[p];
if(ans[top]==s2[p+1]) p++;
fail[top]=p;
if(p==l2) top-=l2;
}
for(int i=1;i<=top;i++) printf("%c",ans[i]);
}
int main()
{
scanf("%s",s1+1);l1=strlen(s1+1);
scanf("%s",s2+1);l2=strlen(s2+1);
slove();kmp();
return 0;
}
最新文章
- 会务准备期间材料准备工作具体实施总结 ----(vim技巧应用, python信息提取与整合, microsoft word格式调整批量化)
- [转]收集android上开源的酷炫的交互动画和视觉效果:Interactive-animation
- TFS 2013&rdquo;无法移除仍为团队管理员身份的标识&rdquo;
- bootstrap布局两列或者多列表单
- 安装Cocoa 新的依赖管理工具Carthage
- Win32 GDI 非矩形区域剪裁,双缓冲技术
- UIViewAdditions(一个非常方便的工具类用它)
- SQL连接、合并、子查询
- NHibernate教程(8)--巧用组件
- ansible的plugins
- 富文本编辑器Quill(一)简单介绍
- 快速傅里叶变换(FFT)时间复杂度
- 大明A+B
- sql server 备份与恢复系列八 系统数据库备份与恢复分析
- 下载文件的一致性验证之MD5值校验
- java+selenium的helloworld
- vue全家桶+Koa2开发笔记(6)--app开发
- js拼接table查询信息部分
- 机器学习理论基础学习13--- 隐马尔科夫模型 (HMM)
- asp.net DataTable导出 excel的方法记录(第三方)