【BZOJ4755】扭动的回文串（Manacher，哈希）

时间：2023-01-18 19:38:57

【BZOJ4755】扭动的回文串（Manacher，哈希）

题面

BZOJ

题解

不要真的以为看见了回文串就是\(PAM,Manacher\)一类就可以过。

这题显然不行啊。

我们主要考虑如何解决跨串拼接的回文串。

我们直接枚举回文中心，

即使要跨串，在最优情况下，也一定包含了这个回文中心的最长回文串

那么二分+哈希即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ull unsigned long long

#define MAX 222222

const int base=2333;

int n,ans;

char A[MAX],B[MAX],C[MAX];

ull Hash[2][MAX],pw[MAX<<1];

int f[2][MAX];

void Manacher(char *s,int *p)

{

	int mx=0,id=0;

	s[0]='>';

	for(int i=1;i<=n;++i)

	{

		p[i]=mx>i?min(p[2*id-i],mx-i):0;

		while(s[i-p[i]-1]==s[i+p[i]+1])++p[i];

		if(i+p[i]>mx)mx=i+p[i],id=i;

	}

}

ull Calc(int c,int l,int r)

{

	if(!c)return Hash[0][r]-Hash[0][l-1]*pw[r-l+1];

	return Hash[1][l]-Hash[1][r+1]*pw[r-l+1];

}

int Binary(int L,int R)

{

	int l=1,r=min(L,n-R+1),ret=0;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(Calc(0,L-mid+1,L)==Calc(1,R,R+mid-1))ret=mid,l=mid+1;

		else r=mid-1;

	}

	return ret;

}

int main()

{

	scanf("%d",&n);scanf("%s",A+1);scanf("%s",B+1);pw[0]=1;

	for(int i=1;i<=n;++i)pw[i]=pw[i-1]*base;

	for(int i=1;i<=n;++i)Hash[0][i]=Hash[0][i-1]*base+A[i];

	for(int i=n;i>=1;--i)Hash[1][i]=Hash[1][i+1]*base+B[i];

	for(int i=1;i<=n;++i)C[i]=A[i];

	for(int i=1,j=0;i<=n;++i)A[++j]='*',A[++j]=C[i];A[n+n+1]='*';

	for(int i=1;i<=n;++i)C[i]=B[i];

	for(int i=1,j=0;i<=n;++i)B[++j]='*',B[++j]=C[i];B[n+n+1]='*';

	n=n+n+1;Manacher(A,f[0]);Manacher(B,f[1]);

	for(int i=1;i<=n;++i)

	{

		int L=(i-f[0][i]+1)/2,R=(i+f[0][i])/2;

		ans=max(ans,f[0][i]+Binary(L-1,R)*2);

	}

	for(int i=1;i<=n;++i)

	{

		int L=(i-f[1][i]+1)/2,R=(i+f[1][i])/2;

		ans=max(ans,f[1][i]+Binary(L,R+1)*2);

	}

	printf("%d\n",ans);

	return 0;

}

相关文章