danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26240

[POJ 3974]Palindrome

2016年9月25日 14:38 | Comments(0) | Category:题解 | Tags:

Manacher……妙,妙啊……

这个题就要是给一个字符串,输出最大回文字串长度。Manacher即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000005;
char buf[maxn],s[maxn<<1];
int p[maxn<<1];
inline void FactStr(){
	register int i,j=0,n=strlen(buf);
	s[j++]='$';
	s[j++]='#';
	for(i=0;i<n;i++){
		s[j++]=buf[i];
		s[j++]='#';
	}
	s[j]='\0';
}
inline int Manachar(){
	register int i,n=strlen(s);
	register int mx=0,id;
	register int ans=-1;
	for(i=1;i<n;i++){
		if(i<mx)
			p[i]=min(p[2*id-i],mx-i);
		else
			p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])
			p[i]++;
		if((p[i]+i)>mx){
			id=i;
			mx=p[i]+i;
		}
		ans=max(ans,p[i]-1);
	}
	return ans;
}
int main(){
	register int Case=0;
	while(scanf("%s",buf)==1){
		if(buf[0]=='E')
			break;
		Case++;
		FactStr();
		printf("Case %d: %d\n",Case,Manachar());
	}
	return 0;
}