最长回文---hdu3068 (回文串 manacher 算法模板)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

题意很清楚：就是求一个串s的子串中最长回文串的长度；这类题用到了manacher算法

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;const int N = 1e6+;char s[N];
int p[N];
///定义数组p[i]表示以i为中心的(包含i这个字符)回文串半径长
int Manacher(char s[], int len)
{
for(int i=len; i>=; i--)
{
s[i+i+] = s[i];
s[i+i+] = '#';
}
s[] = '$';
len = len* + ;
int Index = , maxlen = ;
///定义maxlen是i位置前所有回文串中能延伸到的最右端的位置,即maxlen=p[i]+i,Index是能达到maxlen的中心下标；
for(int i=; i<len; i++)
{
if(maxlen > i)
p[i] = min(p[Index*-i], maxlen-i);
else
p[i] = ;
while(s[i-p[i]]==s[i+p[i]])
p[i]++;
if(i+p[i]>maxlen)
{
maxlen = i+p[i];
Index = i;
}
}
int ans = ; for(int i=; i<len; i++)
ans = max(ans, p[i]);
///由于加入了其他字符所以就要让结果-1；
return ans - ;
}
int main()
{
while(scanf("%s", s)!=EOF)
{
memset(p, , sizeof(p));
int len = strlen(s);
int ans = Manacher(s, len);
printf("%d\n", ans);
}
return ;
}