bzoj 4755 扭动的回文串

Posted on | Views:

二分 + $Hash​$ .

  • 先补充上多余字符,将回文串全部弄成奇回文串.然后二分 + $Hash$ 预处理出每个位置的最大回文半径.
  • 对于第三种情况,可以枚举回文中心,显然往两边拓展时,过了最大回文半径时就换到另一个串是最优的.于是可以二分在另一个串中的长度, $Hash$ 判断合法性.拼接位置的处理比较麻烦,可以调用补字符前的原串 $Hash$ 值.
  • 时间复杂度 $O(nlogn)$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
typedef unsigned long long ull;
const int MAXN=2e5+10;
const ull Base=137;
ull Pow[MAXN],Hash[4][MAXN],revHash[4][MAXN];
int n,ans=1;
char s[2][MAXN],buf[2][MAXN];
int cnt;
ull calc(int k,int l,int r)
{
	return Hash[k][r]-Pow[r-l+1]*Hash[k][l-1];
}
ull revcalc(int k,int l,int r)
{
	return revHash[k][l]-Pow[r-l+1]*revHash[k][r+1];
}
bool check(int k,int pos,int len)
{
	ull Left=calc(k,pos-len,pos-1);
	ull Right=revcalc(k,pos+1,pos+len);
	return Left==Right;
}
int r[2][MAXN];
int solve(int L,int R)
{
	int l=1,r=min(L,n-R+1),res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(calc(2,L-mid+1,L)==revcalc(3,R,R+mid-1))
			res=mid,l=mid+1;
		else
			r=mid-1;
	}
	return res;
}
int main()
{
	n=read();
	scanf("%s%s",s[0]+1,s[1]+1);
	for(int k=0;k<2;++k)
	{
		for(int i=1;i<=n;++i)
			Hash[k+2][i]=Hash[k+2][i-1]*Base+s[k][i];
		for(int i=n;i>=1;--i)
			revHash[k+2][i]=revHash[k+2][i+1]*Base+s[k][i];
	}
	n=cnt;
	Pow[0]=1;
	for(int i=1;i<=n;++i)
		Pow[i]=Pow[i-1]*Base;
	for(int k=0;k<2;++k)
	{
		for(int i=1;i<=n;++i)
			Hash[k][i]=Hash[k][i-1]*Base+(buf[k][i]);
		for(int i=n;i>=1;--i)
			revHash[k][i]=revHash[k][i+1]*Base+(buf[k][i]);
	}
	for(int k=0;k<2;++k)
	{
		for(int pos=1;pos<=n;++pos)
		{
			int L=1,R=(n-1)>>1;
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(check(k,pos,mid))
					r[k][pos]=mid,L=mid+1;
				else
					R=mid-1;
			}
		}
	}
	for(int i=1;i<=n;++i)
	{
		int L=(i-r[0][i]+1)>>1,R=(i+r[0][i])>>1;
		ans=max(ans,r[0][i]+solve(L-1,R)*2);
	}
	for(int i=1;i<=n;++i)
	{
		int L=(i-r[1][i]+1)>>1,R=(i+r[1][i])>>1;
		ans=max(ans,r[1][i]+solve(L,R+1)*2);
	}
	cout<<ans<<endl;
	return 0;
}