KMP的删除操作

Description：

在字符串$S$中，重复删除同一个字串$T$。直到$T$不在是$S$的字串为止

$|S|\le10^6$

第一眼可能没什么思路，但我想到了开栈。

最初的想法是开一个栈，把$S$中的每个字符依次扔进去。

再同时跑kmp，如果匹配上，就弹出长度为$|T|$的元素。

栈中剩下的就是要保留的元素。

但这个做法没过样例还是很良心的qwq。

很显然，这样没法处理删除后产生的新串。

所以我们开一个辅助数组pos，pos[i]表示S的第i位匹配到的T的长度。

举个例子：whatthemomooofun中第9位pos[9]=2，匹配了mo。

这样我们每次在成功匹配退栈后可以让j跳向栈顶的pos，表示从栈顶继续匹配。

这样就解决了连续的问题🌶★,°:.☆(￣▽￣)/$:.°★ 。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+9;
char s1[N],s2[N];
int stk[N],top,nxt[N],pos[N];
int main()
{
	scanf("%s%s",s1+1,s2+1);
	int len1=strlen(s1+1),len2=strlen(s2+1);
	nxt[0]=-1,nxt[1]=0;
	int j;
	for(int i=2;i<=len2;i++)
	{
		j=nxt[i-1];
		while(~j&&s2[j+1]!=s2[i]) j=nxt[j];
		nxt[i]=j+1;
	}
	j=0;
	for(int i=1;i<=len1;i++)
	{
		stk[++top]=i;
		while(~j&&s2[j+1]!=s1[i]) j=nxt[j];
		j++;
		pos[i]=j;
		if(j==len2)
		{
			int t=len2;
			top-=t;
			j=pos[stk[top]];
			// printf("%d\n",j);
		}
	}
	for(int i=1;i<=top;i++) printf("%c",s1[stk[i]]);
	return 0;
}

n