最长回文 HDU - 3068 马拉车模板题

给出一个只由小写英文字符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

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<queue> #include<vector> #include<map> #include<set> #include<stack> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int M = 1e5 + 10; char a[M]; int n; int len[M<<1]; char tmp[M<<1]; void init() { int i,j=2; tmp[0]='$';tmp[1]='#'; for(i=0;i<n;i++) { tmp[j++]=a[i]; tmp[j++]='#'; } } void manacher(char *Tmp) { int i,id=0,mx=0; len[0]=0; for(int i=1;i<=2*n+1;i++) { if(mx>i) len[i]=min(len[2*id-i],mx-i); else len[i]=1; while(Tmp[i+len[i]]==Tmp[i-len[i]]) {/* if(Tmp[i+len[i]]!=-2) { if(Tmp[i+len[i]]<=Tmp[i+len[i]-2]) len[i]++; else break; } */ len[i]++; } if(mx<i+len[i]) { mx=len[i]+i; id=i; } } } int main() { while(~scanf("%s",&a)) { n=strlen(a); init(); manacher(tmp); int ans=0; for(int i=1;i<=2*n+1;i++) ans=max(ans,len[i]); printf("%d\n",ans-1); } return 0; }