hdu3068 最长回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa abab
Sample Output
4 3
Source
Recommend
lcy | We have carefully selected several similar problems for you:
#include#include #include #define N 110010using namespace std;char a[N],s[N*2];int ans,n,len,p[N*2];//p[i]存处理后的字符串包括i本身的最长回文半径 void manacher(){ int id=0,pos=0,x=0;//pos 已有回文半径覆盖到的最右边界的后一个位置，id pos的回文中心， x 以id为中心的回文半径 for(int i=1;i<=n;i++)//枚举i，表示当前要计算以i为中心的回文半径 { if(pos>i) x=min(p[id*2-i],pos-i); //id*2-i：i关于id在id左边的对称点 //pos-i:可以在已知回文半径覆盖范围内能承受的最大回文半径（包括i本身）， //应该是回文半径覆盖最右端-i+1，但因为pos是右边界的后一个位置，所以+1去掉 else x=1;//因为pos是右边界的后一个位置，所以当pos=i的时候，pos位置还是未知的，归入else while(s[i-x]==s[i+x]) ++x; if(i+x>pos) pos=i+x,id=i;//更新回文半径覆盖最右端 p[i]=x; }}int main(){ while(scanf("%s",a+1)!=EOF) { ans=0,n=0; len=strlen(a+1); s[n=0]='!';//开头结尾加不同的字符，保证不会越界 for(int i=1;i<=len;i++) { s[++n]='#'; s[++n]=a[i]; } s[++n]='#'; s[n+1]='@';//结尾 manacher(); for(int i=1;i<=n;i++) if(p[i]>ans) ans=p[i]; printf("%d\n",ans-1); //p[i]=j ，表示① 包含i，包含预处理加入的'#'的最长回文半径 // ② 包含i，原字符串的最长回文长度+1 //因为处理后的最长回文半径的回文中心 无论是原字符串里的字符，还是‘#’，字符都比‘#’少一个 //所以-1 }}