hdu3068 最长回文（manacher 算法）

题意：

给定字符串，，求字符串中的最长回文序列

解题思路：

manacher 算法

时间复杂度：O(N)

代码：

#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 110010using namespace std;char b[MAXN],a[MAXN<<1];int p[MAXN<<1];int n;int main(){while(scanf("%s",&b[1])!=EOF){int i;for(i=1;b[i]!='\0';++i){a[(i<<1)]=b[i];a[(i<<1)+1]='#';}a[0]='?';a[1]='#';n=(i<<1)+2;a[n]=0;int MaxId,MaxL,id;MaxId=MaxL=0;memset(p,0,sizeof(p));for(int i=1;i<n;++i){if(MaxId>i)p[i]=min(p[2*id-i],MaxId-i);elsep[i]=1;while(a[i+p[i]]==a[i-p[i]])p[i]++;if(p[i]+i>MaxId){MaxId=p[i]+i;id=i;}if(p[i]>MaxL)MaxL=p[i];}printf("%d\n",MaxL-1);}return 0;}

版权声明：本文为博主原创文章，未经博主允许不得转载。

记忆的屏障，曾经心动的声音已渐渐远去。