首页 > 代码库 > 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 最长回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。