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

​​1089 最长回文子串 V2（Manacher算法）​​

基准时间限制：1 秒

空间限制：131072 KB

分值: 0

难度：基础题

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。

输入一个字符串Str，输出Str里最长回文子串的长度。

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