题目描述
给出一个只由小写英文字符 a,b,c,d,…… 组成的字符串 S ,求 S 中最长回文串的长度。
字符串长度为 n。
输入格式
一行小写英文字符a,b,c,d,……组成的字符串 S。
Manancher算法(动态规划)
用法:最长回文字符串
利用回文的镜像也是回文,i和j镜像对称,那么P[i] = P[j]
关键:如何快速计算P?
P就是从该点的最大的回文串的半径。
S: $ # a # b # b # a # &
P[i]: 1 1 2 1 2 5 2 1 2 1 1
- 假设已经找到P[0]~p[i-1]
- R是最大右端点,C是该回文字符串的中心点
- 计算P[i]
若i>=R:令P[i]=1,然后只能暴力中心扩展求P[i]
若i<R:
(1)j被C的回文串包含,P[i] = P[j] = P[2C-i],再用中心拓展法求P[i].
(2)j不被C所包含, P[i] = w = R - i = C + P[c] - i,再用中心拓展法求P[i].
#include<bits/stdc++.h>
using namespace std;
const int N = 11000010;
char s[N] , t[N<<1];
int P[N<<1] ,n;
void manacher(){
int R = 0, C ;
n = strlen(t);
for(int i = 1 ; i < n ; i ++){
if(i < R) P[i] = min(P[(C<<1)-i] , P[C]+C-i);
else P[i] = 1;
//中心拓展法求P[i]
while(t[i+P[i]] == t[i-P[i]]) P[i] ++;
//P[i]是已求得的回文串,那么此时最大的右端点就是P[i]+i
if(P[i] + i > R){
R = P[i] + i;
C = i;
}
}
}
int main(){
gets(s);
int len = strlen(s);
for(int j = 0, i = 0 ; j < len ; j ++){
if(j == 0){
t[i ++] = '$';
t[i ++] = '#';
t[i ++] = s[j];
t[i ++] = '#';
}
else if(j == len - 1){
t[i ++] = s[j];
t[i ++] = '#';
t[i ++] = '&';
}
else{
t[i ++] = s[j];
t[i ++] = '#';
}
}
manacher();
int ans = 1;
for(int i = 0 ; i < n ; i ++) ans = max(ans,P[i]);
printf("%d",ans-1);
}