扩展KMP求卡常
查看原帖
扩展KMP求卡常
228843
wangjinbo楼主2021/7/13 15:36

RT,TLE了几个点,麻烦提供一些卡常方式

另外,为什么第15行和第29行是i + l <= p而不是i+l-1 <= p?是我写假了吗?

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+10;
char s1[maxn],s2[maxn];
int z[maxn],e[maxn];
int main()
{
	scanf("%s %s",s1+1,s2+1);
	int n=strlen(s2+1);
	int p=0,k=2;z[1]=n;
	while(p+1<n&&s2[p+1]==s2[p+2])p++;z[2]=p;
	for(int i=3;i<=n;i++){
		p=k+z[k]-1;
		int l=z[i-k+1];
		if(i+l<=p)z[i]=l;
		else{
			z[i]=max(p-i+1,0);
			while(i+z[i]<=n&&s2[z[i]+1]==s2[i+z[i]])z[i]++;
			k=i;
		}
	}
	int m=strlen(s1+1);
	p=0;k=1;
	while(p+1<=min(m,n)&&s1[p+1]==s2[p+1])p++;
	e[1]=p;
	for(int i=2;i<=m;i++){
		p=k+e[k]-1;
		int l=z[i-k+1];
		if(i+l<=p)e[i]=l;
		else{
			e[i]=max(p-i+1,0);
			while(i+e[i]<=m&&e[i]+1<=n&&s1[i+e[i]]==s2[e[i]+1])e[i]++;
		}
	} 
	long long ans=0;
	for(int i=1;i<=n;i++)ans^=(long long)(z[i]+1)*i;printf("%lld\n",ans);
	ans=0;
	for(int i=1;i<=m;i++)ans^=(long long)(e[i]+1)*i;printf("%lld\n",ans);
	return 0;
}
2021/7/13 15:36
加载中...