51Nod 1089 最长回文子串 V2（Manacher算法）——————Mancher，马拉车算法

红太狼 2022-05-10 14:38 151阅读 0赞

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

## [1089 最长回文子串 V2（Manacher算法）][1089 _ V2_Manacher] ##

基准时间限制：1 秒  
空间限制：131072 KB  
分值: 0  
难度：基础题

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

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。  
输入一个字符串Str，输出Str里最长回文子串的长度。

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

Input  
输入Str（Str的长度 <= 100000)  
Output  
输出最长回文子串的长度L。  
Input示例  
daabaac  
Output示例  
5

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

和上一道题差不多，用Manacher算法都能够解决

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5+7;
    char Ma[MAXN<<1];
    int  Mp[MAXN<<1];
    
    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 id = 0;
            int mx = 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))
            {
        
                    int len = strlen(s);
                    int ans = 0;
                    Manacher(s,len);
                    for(int i=0;i<2*len+2;i++)
                            ans = max(ans, Mp[i]-1);
                    printf("%d\n",ans);
            }
            return 0;
    }

[1089 _ V2_Manacher]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1089