首页 > 代码库 > hdu3068 最长回文串

hdu3068 最长回文串



#include<stdio.h>

#include<iostream>
#include<string.h>
using namespace  std;


char str[210100],str1[210100];
int mark[210100];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int i,j;
while(~scanf("%s",str+1))
{
int Max=0;
int id=0;
for(i=1,j=0;str[i]!=‘\0‘;i++)
{
str1[++j]=‘#‘;
str1[++j]=str[i];
}
str1[0]=‘@‘;
str1[++j]=‘#‘;
int len=i*2+1;
memset(mark,0,sizeof(mark));
int k=0;
for(i=1;i<=len;i++)
{
if(Max>i)
{
mark[i]=min(mark[2*id-i],Max-i);
}
else mark[i]=1;
while(str1[mark[i]+i]==str1[i-mark[i]])
{
mark[i]++;
}
if(mark[i]+i>Max)
{
Max=mark[i]+i;
id=i;
}
if(mark[i]>k) k=mark[i];
}
printf("%d\n",k-1);
}
return 0;
}

hdu3068 最长回文串