求助啊,各位巨佬,#4和#8T了,我用栈也优化不来,有大神能讲一下吗?
查看原帖
求助啊,各位巨佬,#4和#8T了,我用栈也优化不来,有大神能讲一下吗?
61399
iawe楼主2021/1/22 23:10
#include<cstdio>
#include<cstring>
#define maxn 1000010
#define rg register
using namespace std;
char a[maxn],b[maxn];
int f[maxn],nxt[maxn],mp[maxn];
int lena,lenb;
bool flag;
inline void delet(int x)
{
	for(rg int i=x;i<=lena-lenb;i++)
	{
		a[i]=a[i+lenb];
	}
	a[lena-lenb+1]='\0';
	lena-=lenb;
}
inline void pre()
{
	int j;
	nxt[1]=j=0;
	for(rg int i=2,j=0;i<=lenb;i++)
	{
		while(j&&b[i]!=b[j+1])j=nxt[j];
		if(b[i]==b[j+1])j++;
		nxt[i]=j;
	}
}
inline void kmp()
{
	for(rg int i=1,j=0;i<=lena;i++)
	{
		while(j&&(j==lenb||a[i]!=b[j+1]))j=nxt[j];
		if(a[i]==b[j+1])j++;
		f[i]=j;
		if(f[i]==lenb)
		{
			delet(i-lenb+1);
			flag=1;
			return;
		}
	}
}
int main()
{
	scanf("%s%s",a+1,b+1);
	lena=strlen(a+1);
	lenb=strlen(b+1);
	pre();
	kmp();
	while(flag)
	{
		flag=0;
		kmp();
	}
	for(int i=1;i<=lena;i++)printf("%c",a[i]);
	return 0;
}
2021/1/22 23:10
加载中...