[POJ 3974]Palindrome
转载请注明出处：http://danihao123.is-programmer.com/
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;
}
评论 (0)
