BZOJ2565 (最长双回文串)[Manachar]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2565

Manachar算法，另外维护一个l数组和一个r数组，分别代表某位置作为某回文串左边界或右边界时该回文串的最长回文半径。
求出l和r之后扫一遍所有的#位置，l[i]+r[i]-2的最大值即为答案。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=110009;
char s[MAXN];
char Ma[MAXN*2];
int Mp[MAXN*2];
void Manachar(char s[],int len) {
	int l=0;
	Ma[l++]='$';
	Ma[l++]='#';
	for(int i=0;i<len;i++) {
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	Ma[l]=0;
	memset(Mp,0,sizeof(Mp));
	int mx=0,id=0;
	for(int i=1;i<l;i++) {
		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
		while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
		if(i+Mp[i]>mx) {
			mx=i+Mp[i];
			id=i;
		}
	}
}
int l[MAXN*2];
int r[MAXN*2];

int main() {
	while(~scanf("%s",s)) {
		int len=strlen(s);
		Manachar(s,len);
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		int len2=strlen(Ma);
		for(int i=1;i<=len2-1;i++) {
			l[i-Mp[i]+1]=Mp[i];
		}
		for(int i=1;i<=len2-1;i++) {
			l[i]=max(l[i],l[i-1]-1);
		}
		for(int i=len2-1;i>=1;i--) {
			r[i+Mp[i]-1]=Mp[i];
		}
		for(int i=len2-1;i>=1;i--) {
			r[i]=max(r[i],r[i+1]-1);
		}
		int mx=0;
		for(int i=3;i<len2-1;i+=2) mx=max(l[i]+r[i],mx);
		printf("%d\n",mx-2<0?0:mx-2);
	}
}