hdu 3068 最长回文 manacher

时间：2022-10-05 21:46:10

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3068

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba,
abba等
 
题目描述：中文题，不翻译。
算法分析：求解最长回文串的长度，当选O（n）的manacher算法。
 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #define inf 0x7fffffff

 using namespace std;

 typedef long long LL;

 const int maxn=+;

 char str[maxn],s[*maxn+];

 int p[*maxn+],cnt;

 void manacher()

 {

     int mx=,id=;

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

     {

         if (mx>i) p[i]=min(p[*id-i],mx-i);

         else p[i]=;

         for ( ;s[i+p[i] ]==s[i-p[i] ] ;p[i]++) ;

         if (p[i]+i>mx)

         {

             mx=p[i]+i;

             id=i;

         }

     }

     //cout<<p[id]-1<<endl;

     int ans=;

     for (int i= ;i<cnt ;i++) ans=max(ans,p[i]);

     cout<<ans-<<endl;

 }

 int main()

 {

     memset(str,,sizeof(str));

     while (scanf("%s",str)!=EOF)

     {

         cnt=;

         memset(s,,sizeof(s));

         memset(p,,sizeof(p));

         s[cnt++]='$';

         int len=strlen(str);

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

         {

             s[cnt++]='#';

             s[cnt++]=str[i];

         }

         s[cnt++]='#';

         s[cnt]=;

         manacher();

     }

     return ;

 }

相关文章