Tang-Dreamoon's Blog

bzoj 2565 最长双回文串

发表于 | 分类于 ， ，

对马拉车的更深的理解

　　题目链接：bzoj 2565

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：这道题的本质显然是让我们找出以 i 为结尾的最长回文串长度加上以 i+1 为开头的最长回文串长度。我们可以发现这两者在本质上是一样的，所以我们考虑如何求出以 i 为结尾的最长回文串长度。考虑马拉车算法的实现时，我们可以发现对于一个点 X 来说，它有可能会在多个回文串中出现，并可以作为它们的结尾。那么哪一个会是最长的呢？答案是第一个暴力匹配到点 X 的回文串是最长的。证明：在第一个暴力匹配到 X 的回文串之前，不会有回文串包含点 X；而在这个回文串之后的回文串中，哪怕它包含点 X，但它的回文中心一定大于这个串，所以长度会小于这个串。所以我们在一边跑马拉车算法的时候就可以求出以每一个点为结尾的最长回文串长度，然后再倒着跑一边马拉车就可以求出来以每一个点为开头的最长回文串长度了，最后枚举中心统计答案。

　　我思故我在：要掌握对题目的本质的翻译的能力，即对于冗长的题目，准确的找出它本质是要求我们在求什么问题。还有就是写代码时，对于相似的模板不可轻易复制，对于需要改变的细节，一定认真找出并改变。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char ap[100005];
char map[100005*3];
int lena[100005*3];
int from[100005*3];
int last[100005*3];
inline int max(int a,int b)
{
	return a > b ? a : b ;
}
int main()
{
	scanf("%s",ap+1);
	int n=strlen(ap+1);
	for(int i=1;i<=n;i++)
	{
		map[i*2-1]='*';
		map[i*2]=ap[i];
	}
	map[n*2+1]='*';
	lena[1]=0;
	int now=1;
	for(int i=2;i<=n*2+1;i++)
	{
		if(from[i]==0) from[i]=i;
		if(i<=now+lena[now])
		{
			int x=now-(i-now);
			if(x-lena[x]>now-lena[now]) lena[i]=lena[x];
			else
			{
				int j=now+lena[now]-i+1;
				while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) from[i+j]=i,j++;
				now=i,lena[i]=j-1;
			}
		}
		else
		{
			int j=1;
			while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) from[i+j]=i,j++;
			now=i,lena[i]=j-1;
		}
	}
	memset(lena,0,sizeof(lena));
	lena[n*2+1]=0;
	now=n*2+1;
	for(int i=n*2;i>=1;i--)
	{
		if(!last[i]) last[i]=i;
		if(i>=now-lena[now])
		{
			int x=now+(now-i);
			if(x+lena[x]<now+lena[now]) lena[i]=lena[x];
			else
			{
				int j=i-(now-lena[now])+1;
				while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) last[i-j]=i,j++;
				now=i,lena[i]=j-1;
			}
		}
		else
		{
			int j=1;
			while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) last[i-j]=i,j++;
			now=i,lena[i]=j-1;
		}
	}
	int ans=0;
	for(int i=2;i<=(n-1)*2;i+=2)
	{
		int x=i-from[i];
		int y=last[i+2]-(i+2);
		int p=(x+1)/2*2;
		int q=(y+1)/2*2;
		if((x%2)==0) p++;
		if((y%2)==0) q++;
		ans=max(ans,p+q);
	}
	cout<<ans<<endl;
	return 0;
}