「USACO15FEB」Censoring (Silver) 审查(银) 解题报告

题面

就是让你——在字符串A中，如果字符串B是A的子串，那么就删除在A中第一个出现的B，然后拼接在一起，一直重复上述步骤直到B不再是A的子串

|A|\(\le 10^6\)

思路：

KMP+栈

1、由于是两个字符串匹配的问题，当然一下子就会想到KMP

2、由于是删去一段区间，很多人第一反应会想到链表，但是在这里，其实删除了一段后，对之前是没有影响的，并且，一定是从后往前删除，所以，更优的存储结构应该是栈。

3、有人会问，为什么删去对前面没有影响，这就根据KMP的原理，做到i这个位置的结果就是最优的，我们只需要用f数组记录一下KMP匹配的结果（f[i]表示以i结尾最大能匹配多长的字符串）。

如何进行？

1、KMP板子跑一遍

2、在KMP过程中，把遍历到的i（不是字符，而是下标）入栈，当匹配到一个完整的串时，把这一整串出栈，然后j从栈顶的i所能匹配到的最大的位置开始（就是f[i]记录的值），继续做KMP

时间复杂度：B自身匹配一次+A与B匹配一次+A中最多每个字符进出栈一次，这么说来时间复杂度还是线性的

于是，代码就很好构造了

Code：

#include<bits/stdc++.h>

#define N 1000010

using namespace std;

int la,lb,res;

char a[N],b[N];

int p[N],f[N];//分别表示B串自身匹配的结果、A串与B串匹配的结果

int St[N],top;//模拟栈，STL的栈也是可以的，就是比较低效

int main()

{

	int i,j;

	scanf("%s",a+1);

	scanf("%s",b+1);

	la=strlen(a+1);

	lb=strlen(b+1);

	for(i=2,j=0;i<=lb;i++)//自身匹配

	{

		while(j&&b[i]!=b[j+1])

			j=p[j];

		if(b[i]==b[j+1])

			j++;

		p[i]=j;

	}

	for(i=1,j=0;i<=la;i++)//A与B匹配

	{

		while(j&&a[i]!=b[j+1])

			j=p[j];

		if(a[i]==b[j+1])

			j++;

		f[i]=j;//记录结果

		St[++top]=i;//入栈

		if(j==lb)//如果匹配成功

		{

			res=lb;

			while(res)//出栈，res记录应该出多少字符

				res--,top--;

			j=f[St[top]];//更新j值

		}

	}

	for(i=1;i<=top;i++)//大功率输出

		printf("%c",a[St[i]]);

	return 0;

}

巴特西

「USACO15FEB」Censoring (Silver) 审查(银) 解题报告

题面

就是让你——在字符串A中，如果字符串B是A的子串，那么就删除在A中第一个出现的B，然后拼接在一起，一直重复上述步骤直到B不再是A的子串

|A|\(\le 10^6\)

思路：

KMP+栈

如何进行？

推荐题目：

最新文章

热门文章