bzoj 2565 最长双回文串

Posted on | Views:

$Manacher$ .

考虑枚举 $X,Y$ 两个回文串的分界位置,不能以首尾的 ‘#’ 作为分界位置,否则 $X,Y$ 长度可以为 $0$ .

利用 $Manacher$ ,位置 $i$ 作为分界位置的贡献就是左边能覆盖到 $i$ 的最大长度加上右边能覆盖到 $i$ 的最大长度.

以找左侧最优位置为例,从左往右扫描,同时维护一个当前处理到的右边界 $k$ .

扫描到第 $i$ 位时,就把 $k+1\sim i+R(i)-1$ 这一段的最优位置全部更新为 $i$ ,然后将右边界更新为 $i+R(i)-1$ .

右边界只会向右移动,所以时间复杂度为 $O(n)$ .

右侧最优位置的处理方法同理.

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
#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;
}
const int MAXN=2e5+10;
char buf[MAXN],s[MAXN];
int n,R[MAXN],sum[MAXN];
void Manacher()
{
	s[0]='$';
	for(int i=1;i<=n;++i)
	{
		s[2*i-1]='#';
		s[2*i]=buf[i];
	}
	s[2*n+1]='#';
	s[2*n+2]='@';
	n=2*n+2;
	int p=0,mx=0;
	for(int i=1;i<n;++i)
	{
		if(mx<i)
			R[i]=1;
		else
			R[i]=min(mx-i+1,R[2*p-i]);
		while(s[i-R[i]]==s[i+R[i]])
			++R[i];
		if(i+R[i]-1>mx)
			mx=i+R[i]-1,p=i;
	}
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+('a'<=s[i] && s[i]<='z');
}
int lp[MAXN],rp[MAXN];
int main()
{
	scanf("%s",buf+1);
	n=strlen(buf+1);
	Manacher();
	int k=0;
	for(int i=1;i<n;++i)
	{
		for(int j=k+1;j<=i+R[i]-1;++j)
			lp[j]=i;
		k=max(k,i+R[i]-1);
	}
	k=n;
	for(int i=n-1;i>=1;--i)
	{
		for(int j=k-1;j>=i-R[i]+1;--j)
			rp[j]=i;
		k=min(k,i-R[i]+1);
	}
	int ans=0;
	for(int i=3;i<n-2;++i)
		if(i&1)
		{
			int t=2*(sum[i]-sum[lp[i]-1])-sum[lp[i]]+sum[lp[i]-1];
			t+=2*(sum[rp[i]]-sum[i-1])-sum[rp[i]]+sum[rp[i]-1];
			ans=max(ans,t);
		}
	cout<<ans<<endl;
	return 0;
}