HDU 3068 最长回文——————Manacher

蔚落 2022-05-09 12:20 224阅读 0赞

## 最长回文 ##

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 30806 Accepted Submission(s): 11310

#### 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

--------------------

Manacher裸题

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 110000+9;
    char Ma[MAXN*2];
    int  Mp[MAXN*2];
    
    char s[MAXN];
    
    void Manacher(char *s, int len)
    {
        
            int l=0;
            Ma[l++]='$';
            Ma[l++]='#';
            for(int i=0;i<len;i++)
            {
        
                    Ma[l++]=s[i];
                    Ma[l++]='#';
            }
            Ma[l]=0;
            int mx=0,id=0;
            for(int i=0;i<l;i++)
            {
        
                    Mp[i]=mx>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;
                    }
            }
    }
    int main()
    {
        
            while(scanf("%s",s)==1)
            {
        
                    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<<ans<<endl;
            }
            return 0;
    }