hdu 3068 最长回文 manacher

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

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba,
abba等
 
题目描述:中文题,不翻译。
算法分析:求解最长回文串的长度,当选O(n)的manacher算法。
 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define inf 0x7fffffff
using namespace std;
typedef long long LL;
const int maxn=+;
char str[maxn],s[*maxn+];
int p[*maxn+],cnt;
void manacher()
{
int mx=,id=;
for (int i= ;i<cnt ;i++)
{
if (mx>i) p[i]=min(p[*id-i],mx-i);
else p[i]=;
for ( ;s[i+p[i] ]==s[i-p[i] ] ;p[i]++) ;
if (p[i]+i>mx)
{
mx=p[i]+i;
id=i;
}
}
//cout<<p[id]-1<<endl;
int ans=;
for (int i= ;i<cnt ;i++) ans=max(ans,p[i]);
cout<<ans-<<endl;
}
int main()
{
memset(str,,sizeof(str));
while (scanf("%s",str)!=EOF)
{
cnt=;
memset(s,,sizeof(s));
memset(p,,sizeof(p));
s[cnt++]='$';
int len=strlen(str);
for (int i= ;i<len ;i++)
{
s[cnt++]='#';
s[cnt++]=str[i];
}
s[cnt++]='#';
s[cnt]=;
manacher();
}
return ;
}
上一篇:Elasticsearch java api 常用查询方法QueryBuilder构造举例


下一篇:HDU - 3068 最长回文(manacher)