P4324

来个考场上的 $O(n\log n)$ 二分哈希做法。

看到回文串，想到先选定回文中心。如果只有一个序列自然是可以直接二分的。但是有两个序列还要选一个折点。怎么选？

我们发现在回文中心所在序列向两端拓展尽可能远是不劣的。钦定中心在 $A$，如果可以先换行走到 $B_i$，又可以直接走到 $A_i$，因为两种走法到 $B_i$ 的距离是相同的，所以可以直接走到 $A_i$ 再一步到 $B_i$。反过来，如果先换行，就不能走回去。

所以先确定中心，二分出最长回文半径，找到折点，再在这个基础上进行一次二分，求出最大答案。

自然溢出 hash 其实是可以的，只要给每个字符赋一个随机权值就行。

还有一个小处理就是发现这样无法解决回文串长为偶数的情况，所以我们可以把字符串变成这样（以样例为例）：

*A*B*C*D*E**
**B*A*E*C*B*

就可以解决了。

code：

int n,m;
ull c[207],f[N][2],g[N][2],pw[N];
char str[N],s[N],t[N];
mt19937 rnd(time(0));
const ull base=114514191811ull;
il ull getHash(int l,int r,int op,int fl){
	if(!fl){
		if(!op){
			return f[r][0]-f[l-1][0]*pw[r-l+1];
		}
		return f[l][1]-f[r+1][1]*pw[r-l+1];
	}
	if(!op){
		return g[r][0]-g[l-1][0]*pw[r-l+1];
	}
	return g[l][1]-g[r+1][1]*pw[r-l+1];
}
void Yorushika(){
	scanf("%d%s",&n,str+1);
	rep(i,1,n){
		s[i+i-1]='*',s[i+i]=str[i];
	}
	s[n+n+1]=s[n+n+2]='*';
	scanf("%s",str+1);
	rep(i,1,n){
		t[i+i+1]=str[i],t[i+i]='*';
	}
	t[1]=t[n+n+2]='*';
	n=n+n+2;
	rep(i,0,200){
		c[i]=1ull*rnd()*rnd()*rnd()*rnd();
	}
	pw[0]=1;
	rep(i,1,n){
		pw[i]=pw[i-1]*base;
	}
	rep(i,1,n){
		f[i][0]=f[i-1][0]*base+c[s[i]];
		g[i][0]=g[i-1][0]*base+c[t[i]];
	}
	drep(i,n,1){
		f[i][1]=f[i+1][1]*base+c[s[i]];
		g[i][1]=g[i+1][1]*base+c[t[i]];
	}
	int tans=0;
	rep(i,1,n){
		int l=1,r=min(i,n-i+1),ans=1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getHash(i-mid+1,i+mid-1,0,0)==getHash(i-mid+1,i+mid-1,1,0)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		int L=i-ans+1,R=i+ans-1;
		l=0,r=min(L-1,n-R+1),ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getHash(L-mid,L-1,0,0)==getHash(R,R+mid-1,1,1)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		tans=max(tans,i-L+1+ans);
	}
	rep(i,1,n){
		int l=1,r=min(i,n-i+1),ans=1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getHash(i-mid+1,i+mid-1,0,1)==getHash(i-mid+1,i+mid-1,1,1)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		int L=i-ans+1,R=i+ans-1;
		l=0,r=min(L,n-R),ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getHash(L-mid+1,L,0,0)==getHash(R+1,R+mid,1,1)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		tans=max(tans,i-L+1+ans);
	}
	printf("%d\n",tans-1);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}