自动搬运

查看原文

来自洛谷，原作者为

	pxb0801 平行世界，多元生活，既可以朝九晚五，又能够浪迹天涯

搬运于2025-08-24 22:32:05，当前版本为作者最后更新于2022-09-06 23:02:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

0.题目大意：

这道题题意已经十分简洁，我就不再过多赘述了。

1.思考过程：

首先看到数据范围，发现 $1≤$ 原字符串长度 $≤10^6$，我不禁倒吸一口凉气：暴力做不了了。

为什么不行呢？因为这题不仅仅是要求子串，关键是删完子串后还要合并，这个时间是 $O(n^2)$ 级别的。

看到这，你知道怎么做了吗？

哦，我听到有人说用栈。没错，这道题我就给大家用栈来做一做。

2.分析：

首先我们需要一个 $st[]$ 数组，用于记录放入栈的字符；我们还需要一个 $w[]$ 数组，用于记录放入栈的字符是在子串中的位置，即第几个。

接下来我们开始从头遍历原字符串。如果我们发现此时遍历的字符既不是子串的第一个字符，也不是子串的 $w[top]+1$ 位，即没有连着前面的字符，则栈内元素全部输出，再输出当前字符。

如果满足当中任意一个条件，则放入栈中。如果发现此字符的位置已是子串的结尾字符，则直接将 $top$ 减掉。

最后，如果栈内还有字符，说明这些是最后未被删除的，也应输出。

3.正确代码

不要抄袭哦~

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
char st[1000005];
int l1,l2,top,w[1000005];
int main(){
	ios::sync_with_stdio(false);
	cin>>s1>>s2;
	l1=s1.size();
	l2=s2.size();
	s2=" "+s2;
	bool ok=0;
	for(int i=0;i<l1;i++){
		if(s1[i]!=s2[w[top]+1]&&s1[i]!=s2[1]){
			for(int j=1;j<=top;j++){
				cout<<st[j];
			}
			top=0;
			cout<<s1[i];
			ok=1;
//			cout<<top<<" "<<s1[i]<<" "<<111111<<endl;
			continue;
		}
		st[++top]=s1[i];
		if(s1[i]!=s2[w[top-1]+1]){
			w[top]=1;
		}
		else{
			w[top]=w[top-1]+1;
		}
		if(w[top]==l2){
			top-=l2;
		}
//		cout<<top<<" "<<s1[i]<<endl;
	}
	for(int i=1;i<=top;i++){
		cout<<st[i];
		ok=1;
	}
	if(!ok) cout<<"FRULA";
    return 0;
}

4.写在后面：

本蒟蒻的第一篇题解，望过，谢谢！