作者是个*
题目描述
原题来自：USACO 2015 Feb. Silver
给出两个字符串(S)和(T)，每次从前往后找到(S)的一个子串(T)并将其删除，空缺位依次向前补齐，重复上述操作多次，直到(S)串中不含(T)串。输出最终的(S)串。
输入格式
第一行包含一个字符串(S)，第二行包含一个字符串(T)。
输出格式
输出处理后的(S)串。
样例
样例输入
whatthemomooofun
moo
样例输出
whatthefun
思路
一看这道题，我们会有这几种想法
1：线段树爆搞
2：(Hash + 栈)
3：(KMP + 栈)
由于本人太菜，暂时先讲 (法2) ，日后在更 (法3)。
首先，我们要想一想怎么用(Hash)
我们知道两个字符串的长度，显然，我们可以在计算(S)字符串某一位是直接用(Hash)判断
但是，由于当你删除之后可能重新出现一个(T)串，所以，我们用栈维护
我们每一次，都把当前的字符的下标扔进栈，哈希就在栈中计算，算完之后在判断。
代码大概长这样！！！
/************************************************
*Author : xzj213
*Created Time : 2020.01.17.14:21
*Mail : xzj213@qq.com
*Problem : LOJ10048
************************************************/
#include <bits/stdc++.h>
#define REP(i,a,b) for(register int i=(a);i<=(b);i++)
#define DREP(i,a,b) for(register int i=(a);i>=(b);i--)
#define mem(a,x) memset((a),(x),sizeof(a))
#define pii pair<int,int>
#define lson k<<1
#define rson k<<1|1
#define x first
#define y second
#define int long long
#define str(a) strlen(a)
using namespace std;
const int maxn=1e6+5;
const int base=211,Mod=19491001;
string s1,s2;
int Hash[maxn],p[maxn],S2,len1,len2,top,st[maxn];
/*
Hash[i] 表示栈中的第i位的Hash值
p[i] 表示base的i次方，用于计算S中某一段的Hash值
st[i] 表示栈 top 表示栈顶位置
*/
void chkmax(int &a,int b){if(a<b)a=b;}
void chkmin(int &a,int b){if(a>b)a=b;}
int read() {
int x=0,f=1;
char ch=getchar();
while(ch>57 || ch<48){if(ch==45)f=-1;ch=getchar();}
while(ch<=57 && ch>=48){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main() {
cin>>s1>>s2;
len1=s1.size();
len2=s2.size();//输入
p[0]=1;
REP (i,1,maxn-1) p[i]=p[i-1]*base%Mod;
REP (i,0,len2-1) S2=(S2*base+s2[i])%Mod;
//计算 p[] 和 T 的Hash值
REP (i,0,len1-1) {
st[++top]=i;
Hash[top]=(Hash[top-1]*base+s1[i])%Mod;
if (top>=len2 && ((Hash[top]-Hash[top-len2]*p[len2])%Mod+Mod)%Mod==S2) top-=len2;
//判断S中是否T这个字符串
}
for (int i=1;i<=top;i++)
cout<<s1[st[i]];//输出
puts("");//换行
return 0;//~~提交就可以AC啦！！~~
}