【题目大意】

有一个S串和一个T串,长度均小于1,000,000,设当前串为U串,然后从前往后枚举S串一个字符一个字符往U串里添加,若U串后缀为T,则去掉这个后缀继续流程。

【样例输入】

whatthemomooofun
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 ;
}

最新文章

  1. kvm虚拟机--存储池配置梳理(转)
  2. Unity3D热更新全书-脚本(四) 用C#LightEvil搭建实际开发使用的脚本框架
  3. SCP 命令(转)
  4. CentOS下安装setuptools、pip和virtualenv
  5. SPRING IN ACTION 第4版笔记-第五章BUILDING SPRING WEB APPLICATIONS-003-示例项目用到的类及配置文件
  6. C#学习笔记一:C#开发环境的设置
  7. 使用WMI控制Windows进程 和服务
  8. 详细解析 RxAndroid 的使用方式
  9. 加密解密技术—Web.config加密和解密
  10. 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165317
  11. [CQOI2018]九连环
  12. Netsharp配置文件
  13. 在Linux里安装Samba(文件共享)方便在Windows下面操作
  14. MySQL binlog 组提交与 XA(两阶段提交)--1
  15. Elasticsearch Query DSL 整理总结(三)—— Match Phrase Query 和 Match Phrase Prefix Query
  16. &quot;is not allowed to connect&quot; mysql
  17. vps hiformance 设置备忘
  18. C#程序集系列11,全局程序集缓存
  19. Java反射API研究(3)——java.lang.Class&lt;T&gt;
  20. 洛谷 P3659 [USACO17FEB]Why Did the Cow Cross the Road I G

热门文章

  1. MySQL FEDERATED 存储引擎的使用
  2. bzoj 2131 免费的馅饼
  3. asp.net core microservices 架构之 分布式自动计算(二)
  4. Bean后置处理器 BeanPostProcessor
  5. Shell编程(二)——shell的基础知识及常用命令
  6. 在Mac中安装python,配置python环境
  7. 利用git bash和git gui向git远程仓库提交文件
  8. Eclipse自动生成 get/set
  9. Linux常用命令(个人使用频率较高)
  10. slabtop 监控实时内核片缓存信息