hdu 3068最长回文

使用o(n)的manacher算法,详见代码

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<iterator>
#include<vector>
#include<set>
#define dinf 0x3f3f3f3f
typedef long long ll;
//const int Max=(1<<16)+10;
using namespace std;
#define SIZE 1000005 char tmp[SIZE],s[SIZE];//tmp存变换后的串,s存原串
int p[SIZE];//存以mid为中心的回文串的长度 void init()
{
int slen=strlen(s);
tmp[]='$'; //头标记防止越界
for(int i=,j=;i<=*slen+;i+=)
{
tmp[i]='#';
tmp[i+]=s[j++];
}
tmp[*slen+]='#';//尾标记
} int manacher()
{
int mid=,mx=,ans=;//mx为当前计算回文串最右边字符位置最大值
int tlen=strlen(s)*+;
for(int i=;i<=tlen;i++)
{
if(mx>i)
p[i]=min(mx-i,p[*mid-i]);
else //i>mx从头开始匹配
p[i]=;
while(tmp[i-p[i]]==tmp[i+p[i]])
p[i]++;
if(p[i]+i>mx)//计算得到的右端点值大于mx则进行更新
{
mx=p[i]+i;
mid=i;
}
ans=max(ans,p[i]);
}
return ans-;//p[i]-1即最长回文串的长度
} int main()
{
while(scanf("%s",&s)!=EOF)
{
init();
printf("%d\n",manacher());
}
return ;
}
上一篇:Python | 文件/文件夹的压缩及解压缩和信息读取


下一篇:Linux下 虚拟串口的生成(程序)