社区讨论

z函数72pts求查错

P5410【模板】扩展 KMP / exKMP(Z 函数)参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lob727k1
此快照首次捕获于
2023/10/29 16:13
2 年前
此快照最后确认于
2023/11/03 22:33
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int z[60000000];
string b,a,c;int al,bl;long long ans1,ans2;
void get_z(){
	
	c=b+a;
	int cl=c.length();
	z[1]=1;
//	cout<<c<<" "<<cl<<endl;;
	int l=0;
    for(int i=1;i<cl;i++){
        if(l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
        while(i+z[i]<cl&&c[z[i]]==c[i+z[i]]) z[i]++;
        if(i+z[i]>l+z[l]) l=i;
    }
}

int main(){
//	freopen("P5410_1.in","r",stdin);
	cin>>a>>b;al=a.length(),bl=b.length();
	get_z();
//	for(int i=0;i<=al+bl;i++)cout<<z[i]<<" ";cout<<endl;
//	ans1^=1ll*(bl+1);
	for(int i=0;i<bl;i++)
		ans1^=1ll*(min(z[i],bl-i)+1)*(i+1);
	for(int i=0;i<al;i++)
		ans2^=1ll*(min(z[i+bl],bl)+1)*(i+1);
	cout<<ans1<<endl<<ans2;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...