stdKonjac's Blog

 要做到不可替代,就要与众不同。

【删除子串】

题目背景

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

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.