hdu3068——最长回文-白红宇

hdu3068——最长回文

阅读量：2344 次

发布时间：2019-05-10

本文共 925 字，大约阅读时间需要 3 分钟。

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

题意就是求最长回文字串的长度

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        //#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #define MAXN 110010#define mod 2012#define INF 0x3f3f3f3fusing namespace std;char Ma[MAXN*2];int Mp[MAXN*2];void Manacher(char s[],int len){ int l=0; Ma[l++]='$'; Ma[l++]='#'; for(int i=0;i
              
               i?min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++; if(i+Mp[i]>mx) { mx=i+Mp[i]; id=i; } }}char s[MAXN];int main(){ ios::sync_with_stdio(false); while(cin>>s) { int len=strlen(s); Manacher(s,len); int ans=0; for(int i=0;i<2*len+2;i++) ans=max(ans,Mp[i]-1); cout<
               
                <