自动搬运

查看原文

来自洛谷，原作者为

	hovny <vSiLenCe^>

搬运于2025-08-24 22:04:19，当前版本为作者最后更新于2018-12-26 14:24:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathtt{Update\ 2019.11.08}$

题面

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

|A|$\le 10^6$

解题思路

KMP+栈

分析

1、字符串匹配的问题，想到 $KMP$

2、在匹配过程中，如果匹配成功了，就将子串 $B$ 删除，可以证明，对之前不会产生影响

3、删了再加入，类似栈的操作，因此用栈维护上述操作过程中的字串即可

过程

1、$KMP$ 板子跑一遍

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

时间复杂度：$B$ 自身匹配一次 $+A$ 与 $B$ 匹配一次$+A$ 中最多每个字符进出栈一次，为 $O(|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;
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)//如果匹配成功，弹出，并更新j值
			top-=lb,j=f[St[top]];
	}
	for(i=1;i<=top;i++)//大功率输出
		printf("%c",a[St[i]]);
	return 0;
}

再扔道题 Luogu P3121 [USACO15FEB]审查（黄金）Censoring (Gold)