1. 首页
  2. KMP, 代码宅, 字符串算法

【删除子串】

题目背景

USACO 2015 FEBRUARY CONTEST,SILVER——PROBLEM 1 CENSORING

题目描述

给定一个字母串 S 和一个字母串 T ,所有字母都由小写字母 a..z 构成,S 和 T 的长度均不超过 1,000,000 ,T 的长度不会超过 S 。另外有一个空串 U 。
从左往右枚举 S 串的每个字符,每枚举一个字符,则往 U 串里添加一个字符,若某个时候U串的后缀为 T ,则删掉这个后缀,继续添加,直到 S 串全部枚举完成为止。
请你输出最后的 U 串。

输入格式

输入的第一行是字符串 S ,第二行是字符串 T 。

输出格式

输出最后的 U 串。数据保证 U 串不会为空串。

样例数据 1

输入

whatthemomooofun
moo

输出

whatthefun

备注

【样例说明】
当添加到 whatthemomoo 时,删除 moo ,得到 whatthemo ;
继续添上 o ,得到 whatthemoo ,再次删除 moo ,得到 whatthe ;
继续添上 fun ,最后得到 whatthefun 。

一道KMP题……先用KMP求出next数组然后看到第i位最多能匹配多少个字符,如果匹配不完全就把这个字符加入栈,如果匹配完全了就把配对字串出栈,pos继承配对字串起始位置前一个字符的配对个数继续配对……手残想到了实现不了真是无限悲伤QAQ

下面是代码:

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~