51Nod 1088 最长回文子串——————Manacher,马拉车算法

深藏阁楼爱情的钟 2022-05-10 14:36 224阅读 0赞

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

## [ 51Nod 1088 最长回文子串][51Nod 1088] ##

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

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

回文串是指 &ThickSpace; a b a 、 a b b a 、 c c c b c c c 、 a a a a \\;aba、abba、cccbccc、aaaa aba、abba、cccbccc、aaaa这种左右对称的字符串。  
输入一个字符串 S t r Str Str，输出 S t r Str Str里最长回文子串的长度。

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

#### Input ####

输入Str（Str的长度 <= 1000)

#### Output ####

输出最长回文子串的长度L。

#### Input示例 ####

daabaac

##### Output示例 #####

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

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e4+7;
    char s[MAXN];
    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<len;i++)
            {
        
                    Ma[l++]=s[i];
                    Ma[l++]='#';
            }
            Ma[l] = 0;
            int id = 0;//
            int mx = 0;//mx 代表以 id 为中心的最长回文的右边界
            for(int i=0;i<l;i++)
            {
        
                    Mp[i] = mx>i?min(Mp[2*id-i],mx-i):1;// 2*id-i 是 i 关于 id 的对称点
                    while(Ma[i + Mp[i]] == Ma[i - Mp[i]] )//左侧字符和右侧字符相等的话，就让Mp[i]++
                            Mp[i]++;
                    if(i + Mp[i] > mx)//更新mx 和 id 的值
                    {
        
                            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;
    }

[51Nod 1088]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1088