自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 22:54:33，当前版本为作者最后更新于2024-02-26 16:42:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题的题号在我们学校信息队有着特殊的意义，所以前来写了一下。

回文，但是在加起来之后。

Manacher 死透了，那剩下能快速判回文的方法就是哈希了，即回文串的前后两半的正反哈希相同。正好我们惊喜地发现只要底数够大（$>200$），哈希结果就是可以相加的！看起来非常符合本题要求。

发现由于回文性质，奇数答案和偶数答案是分别可以二分的。考虑对于奇数和偶数分别二分答案 $mid$，现在问题就变为怎么判断存不存在相加后长度为 $mid$ 的回文串。

钦定 $mid$ 是偶数。首先在 $A,B$ 中正着和反着求一遍所有长度为 $\frac{mid}{2}$ 的子串的哈希值。设串 $s$ 的正反哈希值分别为 $h_s,h'_s$。

然后如果存在合法回文串，$A,B$ 中就分别需要存在两个相邻的长度均为 $\frac{mid}{2}$ 的子串 $a_1,a_2$ 和 $b_1,b_2$，满足 $h_{a_1+b_1}=h'_{a_2+b_2}\implies h_{a_1}+h_{b_1}=h'_{a_2}+h'_{b_2}\implies h_{a_1}-h'_{a_2}=h'_{b_2}-h_{b_1}$。

你发现 $(a_1,a_2),(b_1,b_2)$ 都只有 $O(n)$ 对，所以直接预处理出所有可能的 $h_{a_1}-h'_{a_2}$ 和 $h'_{b_2}-h_{b_1}$ 的结果然后扔进 map 看一下有没有相等的即可。

$mid$ 是奇数同理，中间隔了一个而已。或许还可以用 Manacher 的技术在中间空位补几个数然后对奇数偶数一视同仁，但是不太确定 $A,B$ 会不会因为错位匹配挂掉。

复杂度 $O(n\log^2 n)$。有点小卡常，开 unordered_map 会好点。注意哈希值相减的时候不要变成负数。

const ll J=1e18,N=1e5+7,B[2]={211,213},P=1e9+9;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll pw[N][2],pv[N][2];
ll n,m,a[N],b[N],ans;
ll af[N][2],ab[N][2],bf[N][2],bb[N][2];
bool chk(ll len,ll c) {
	unordered_map<ll,ll> mp;
	for (ll i=1;i+len*2+c<=n+1;i++) {
		ll ha[2],hb[2];
		for (ll o=0;o<2;o++)
			ha[o]=(af[i+len-1][o]+P-af[i-1][o]*pw[len][o]%P)%P,
			hb[o]=(ab[i+len+c][o]+P-ab[i+len*2+c][o]*pw[len][o]%P)%P;
		mp[(ha[0]+P-hb[0])%P*P+(ha[1]+P-hb[1])%P]=1;
	}
	for (ll i=1;i+len*2+c<=m+1;i++) {
		ll ha[2],hb[2];
		for (ll o=0;o<2;o++)
			ha[o]=(bf[i+len-1][o]+P-bf[i-1][o]*pw[len][o]%P)%P,
			hb[o]=(bb[i+len+c][o]+P-bb[i+len*2+c][o]*pw[len][o]%P)%P;
		if (mp.count((hb[0]+P-ha[0])%P*P+(hb[1]+P-ha[1])%P)) return 1;
	}
	return 0;
}
void mian() {
	for (ll o=0;o<2;o++) {
		pw[0][o]=1;
		for (ll i=1;i<N;i++) pw[i][o]=pw[i-1][o]*B[o]%P;
		for (ll i=0;i<N;i++) pv[i][o]=qp(pw[i][o]);
	}
	scanf("%lld%lld",&n,&m);
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (ll i=1;i<=m;i++) scanf("%lld",&b[i]);
	for (ll o=0;o<2;o++) {
		for (ll i=1;i<=n;i++) af[i][o]=(af[i-1][o]*B[o]+a[i])%P;
		for (ll i=n;i;i--) ab[i][o]=(ab[i+1][o]*B[o]+a[i])%P;
		for (ll i=1;i<=m;i++) bf[i][o]=(bf[i-1][o]*B[o]+b[i])%P;
		for (ll i=m;i;i--) bb[i][o]=(bb[i+1][o]*B[o]+b[i])%P;
	}
	for (ll c=0;c<2;c++) {
		ll l=0,r=min(n,m)/2,mid,res=0;
		while (l<=r) {
			mid=l+r>>1;
			if (chk(mid,c)) res=mid,l=mid+1;
			else r=mid-1;
		}
		ans=max(ans,res*2+c);
	}
	cout<<ans;
}