manacher

发表于 | 分类于 |

求最长回文子串。

暴力：

枚举某个点为回文中心，向两边扩展。（在每个字符中间再插一个没出现过的字符以保证回文子串长度为偶数的情况）

时间复杂度：$O(N^2)$

然而可以线性时间。

$F_i$表示以$i$点为中心时的回文子串半径最大：cabac以b为中心的回文串的半径$r$为2

根据回文串的性质：左右对称

我们可以得出在某一个回文串中，以它的回文中心右边的某个点为回文中心的最长回文子串长度，不小于以它左边对称点为中心的最长回文子串的长度

于是：

当$i>P$且$i\le P+r$时（$P$为当前的中心），

有$Fi\gee F{P-r}$。

在这基础上再向左右扩展

当然，还有一些特殊情况：出界，右边的回文串长一些（cccbcc中b为中心，最右边）等一些情况。

1
F[i]=max( 0,min( F[2*p-i],p+F[p]-i ) );

理解一下这条语句$2*p-i$原型是$p-(i-p)$

在此基础上再向左右扩展下去

1
while(s[i-F[i]]==s[i+F[i]]) F[i]++;

当以新的$i$点为中心的最长回文子串的边界超过原中心的边界时，这个$i$就升级为新的中心。

贴代码：

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<math.h>
#include<string.h>
//#include<>
using namespace std;
char str[120000],s[240000];
int ans,F[240000];
void pre()
{
	s[0]='@';
	int l=strlen(str);
	for(int i=0;i<l;i++)
	{
		s[i*2+1]='#';
		s[i*2+2]=str[i];
	}
	s[(l-1)*2+3]='#';
	s[(l-1)*2+4]='%';
}
void manacher()
{
	int n=(strlen(str)-1)*2+4;
	F[0]=F[1]=ans=0;
	int p=1;
	for(int i=2;i<=n;i++)
	{
		F[i]=max( 0,min( F[2*p-i],p+F[p]-i ) );
		while(s[i-F[i]]==s[i+F[i]]) F[i]++;
		if(i+F[i]>p+F[p]) p=i;
		ans=max(ans,F[i]);
	}
}
int main()
{
	while(scanf("%s",&str)!=EOF)
	{
		pre();
		manacher();
		printf("%d\n",ans-1);
	}
	return 0;
}

例题：HDU3068（裸题）