为什么TLE
查看原帖
为什么TLE
124918
LinkyChristian楼主2021/10/22 18:39
#include<bits/stdc++.h>
#define N 20000010
using namespace std;
char s[N],t[N];
int slen,tlen,extend[N],nxt[N];
void getnxt()
{
	nxt[0]=tlen;
	int now=0;
    while(t[now]==t[1+now]&&now+1<tlen)now++;//这就是从1开始暴力
    nxt[1]=now;
    int p0=1;
	for(register int i=2; i<tlen; i++) {
		if(i+nxt[i-p0]<nxt[p0]+p0) nxt[i]=nxt[i-p0];
		else {
			now=(nxt[p0]+p0-i,0);
			while(t[now]==t[now+i]&&now+i<tlen) now++;
			nxt[i]=now,p0=i;
		}
	}
}
void exkmp()
{
	getnxt();
    int now=0;
    while(s[now]==t[now]&&now<min(slen,tlen))now++;//暴力
    extend[0]=now;
    int p0=0;
    for(register int i=1; i<slen; i++) {
    	if(i+nxt[i-p0]<extend[p0]+p0) extend[i]=nxt[i-p0];
    	else {
    		now=max(extend[p0]+p0-i,0);
    		while(t[now]==s[i+now]&&now<tlen&&now+i<slen) now++;
    		extend[i]=now,p0=i;
		}
	}
}
int main()
{
	scanf("%s%s",&s,&t);
	slen=strlen(s),tlen=strlen(t);
	exkmp();
	long long ans1=0,ans2=0;
	for(register int i=0; i<tlen; i++) ans1^=1ll*(i+1)*(nxt[i]+1);
	for(register int i=0; i<slen; i++) ans2^=1ll*(i+1)*(extend[i]+1);
	cout<<ans1<<endl<<ans2;
	return 0;
}
2021/10/22 18:39
加载中...