HDU3068 (最长回文)[Manachar]

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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3068

求最长回文子串，Manachar算法模板题，这里贴出Manachar算法模板。

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
#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 main() {
	while(~scanf("%s",s)) {
		int len=strlen(s);
		Manachar(s,len);
		int mx=0;
		for(int i=1;Ma[i]!='\0';i++) {
			if(Mp[i]>mx) {
				mx=Mp[i];
			}
		}
		printf("%d\n",mx-1);
	}
}