【bzoj3942】[Usaco2015 Feb]Censoring
2024-09-28 03:15:36
【题目大意】
有一个S串和一个T串,长度均小于1,000,000,设当前串为U串,然后从前往后枚举S串一个字符一个字符往U串里添加,若U串后缀为T,则去掉这个后缀继续流程。
【样例输入】
whatthemomooofun
moo
moo
【样例输出】
whatthefun
【题解】
我能说这是可持久化的kmp吗?(并没有此种术语)
kmp的过程中,用一个栈来存当前U串,如果匹配到了,弹出即可,然后j指针有恢复到历史的状态,这个状态可以用f数组来存。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1000100
int n,m,top,stack[MAXN],p[MAXN],f[MAXN];
char a[MAXN],b[MAXN];
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
scanf("%s",a+); scanf("%s",b+);
n=strlen(a+); m=strlen(b+);
for(int i=,j=;i<=m;i++)
{
while(j&&b[j+]!=b[i]) j=p[j];
if(b[j+]==b[i]) j++;
p[i]=j;
}
for(int i=,j=;i<=n;i++)
{
j=f[stack[top]];
while(j&&b[j+]!=a[i]) j=p[j];
if(b[j+]==a[i]) j++;
if(j==m) top-=(m-);
else stack[++top]=i,f[i]=j;
}
for(int i=;i<=top;i++) printf("%c",a[stack[i]]);
return ;
}
最新文章
- kvm虚拟机--存储池配置梳理(转)
- Unity3D热更新全书-脚本(四) 用C#LightEvil搭建实际开发使用的脚本框架
- SCP 命令(转)
- CentOS下安装setuptools、pip和virtualenv
- SPRING IN ACTION 第4版笔记-第五章BUILDING SPRING WEB APPLICATIONS-003-示例项目用到的类及配置文件
- C#学习笔记一:C#开发环境的设置
- 使用WMI控制Windows进程 和服务
- 详细解析 RxAndroid 的使用方式
- 加密解密技术—Web.config加密和解密
- 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165317
- [CQOI2018]九连环
- Netsharp配置文件
- 在Linux里安装Samba(文件共享)方便在Windows下面操作
- MySQL binlog 组提交与 XA(两阶段提交)--1
- Elasticsearch Query DSL 整理总结(三)—— Match Phrase Query 和 Match Phrase Prefix Query
- ";is not allowed to connect"; mysql
- vps hiformance 设置备忘
- C#程序集系列11,全局程序集缓存
- Java反射API研究(3)——java.lang.Class<;T>;
- 洛谷 P3659 [USACO17FEB]Why Did the Cow Cross the Road I G