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

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

Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 
两组case之间由空行隔开(该空行不用处理) 
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4

3

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 using namespace std;

 const int N=;

 char a[N];

 char m[N*];

 int f[N*];

 int k;

 void manacher(char *a,int len)

 {

     k=;

     m[k++]='$';

     m[k++]='#';

     for(int i=; i<len; i++)

     {

         m[k++]=a[i];

         m[k++]='#';

     }

     m[k]='\0';//或者加其他的只要不是#$字母都可以

     int mx=,id=;

     for(int i=; i<k; i++) //??

     {

 //      if(mx-i<=ans[i])

 //        ans[i]=mx-i;

 //      else if(mx-i>ans[i])

         if(i>=mx)

             f[i]=;

         else if(i<mx)

         {

 //            f[i]=min(f[2*id-i],mx-i);

             if(mx-i>=f[*id-i])//if(mx-i<=f[j])

                 f[i]=f[*id-i];

             else if(mx-i<f[*id-i])//else if(mx-i<f[j])

                 f[i]=mx-i;

         }

         while(m[i-f[i]]==m[i+f[i]])

             f[i]++;

         if(f[i]+i>mx)

         {

             mx=f[i]+i;

             id=i;

         }

     }

 }

 int main()

 {

     while(~scanf("%s",a))

     {

         int len=strlen(a);

         manacher(a,len);

         int ans=-;

         for(int i=;i<k;i++)

             ans=max(ans,f[i]-);

         printf("%d\n",ans);

     }

     return ;

 }