首页 > ACM题库 > HDU-杭电 > HDU 3068-最长回文[解题报告]HOJ
2014
03-01

HDU 3068-最长回文[解题报告]HOJ

最长回文

问题描述 :

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

输入:

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

输出:

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

样例输入:

aaaa

abab

样例输出:

4
3

#include<stdio.h>
#include<string.h>
#define MAX 110010

char str[MAX],str1[2*MAX];
int mana[2*MAX];
int len;
int ans;

int min(int a,int b)
{
	return a<b?a:b;
}

int max(int a,int b)
{
	return a>b?a:b;
}

void manachar()
{
	int i,j,k;
	memset(mana,0,sizeof(mana));
	str1[0]='&';
	for(i=0,j=1;str[i]!=0;i++)
	{
		str1[j++]='#';
		str1[j++]=str[i];
	}
	str1[j++]='#';
	str1[j]='*';
	len=j;
	i=1;
	int mx=0,id;
	ans=0;
	for(i=1;i<len;i++)
	{
		if(mx>i) mana[i]=min(mx-i,mana[2*id-i]);
		else mana[i]=1;
		for(;str1[i-mana[i]]==str1[i+mana[i]];mana[i]++);
		if(mana[i]+i>mx)
		{
			mx=mana[i]+i;
			id=i;
		}
		if(mana[i]>ans)
			ans=mana[i];
	}
}

int main()
{
	while(scanf("%s",str)!=EOF)
	{
		len=strlen(str);
		manachar();
		printf("%d\n",ans-1);
	}
	return 0;
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。