[USACO15FEB]Censoring S「KMP算法」

2021-04-13 03:29

阅读：703

标签：分析 name att 思路描述模拟 space math for

[USACO15FEB]Censoring S「KMP算法」

题目描述

原题来自：USACO 2015 Feb. Silver

给出两个字符串\(S\)和\(T\)，每次从前往后找到\(S\)的一个子串\(T\) 并将其删除，空缺位依次向前补齐，重复上述操作多次，直到\(S\)串中不含\(T\)串。输出最终的\(S\)串。

输入格式

第一行包含一个字符串\(S\)，第二行包含一个字符串\(T\)。

输出格式

输出处理后的\(S\)串。

样例

样例输入

whatthemomooofun
moo

样例输出

whatthefun

思路分析

如果这题是只有删除或只有查找那就很简单了，关键是这两个放在了一起……
首先我们要明确一点就是删除一个\(T\)串后，可能会出现新的\(T\)串（比如样例），所以我们需要随时更新\(S\)串的状态
因为是线性的遍历，所以模拟一个栈就可以了，栈内存储新\(S\)串下标，每次找到一个\(T\)串就将其整个弹出，维护\(S\)串的状态
另外这里开了两个记录匹配情况的数组，分别记录，板子只开一个是因为一般情况这两个数组是等效的，所以省去了一个，但这题加上删除操作，就不等效了

代码

#include
#include
#include
#include
#include
#define N 1000010
using namespace std;
char s[N],t[N];
int f[N],sta[N],kmp[N],top; //kmp记录t本身的匹配情况，f记录s与t的匹配情况

int main(){
	scanf("%s%s",s+1,t+1);
	int ls = strlen(s+1),lt = strlen(t+1);
	for(int i = 2,j=0;i

[USACO15FEB]Censoring S「KMP算法」

标签：分析 name att 思路描述模拟 space math for

原文地址：https://www.cnblogs.com/hhhhalo/p/13344065.html

上一篇：14、Java文件操作stream、File、IO

下一篇：spring容器&classLoader

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[USACO15FEB]Censoring S「KMP算法」
文章链接：http://soscw.com/index.php/essay/75017.html

亲，登录后才可以留言！

[USACO15FEB]Censoring S「KMP算法」

[USACO15FEB]Censoring S「KMP算法」

题目描述

输入格式

输出格式

样例

样例输入

样例输出

思路分析

代码

评论

热门文章

推荐文章

最新文章

置顶文章