最大回文子串----Manacher

思路：

先把原字符串扩充 然后遍历扩充后的数组 用maxx存放最大回文长度 len数组存放他每个下标的的会问长度

时间复杂度O(n)

Code：

#include<iostream>
#include<cmath>
#include<string.h>
using namespace std;
const int N = 1.1e7 + 5;
char s1[N], s2[N * 2];//字符串开N的空间 他的扩展串的空间得开2N
int len[N * 2];//存扩展串长度也得开2N
int maxx, lens;
void gets2()
{
    int k = 0;
    s2[k++] = '@';//扩展串的第一个不能为字母或者‘#’
    lens = strlen(s1);//求原字符串的长度
    for (int i = 0; i < lens; i++)
    {
        s2[k++] = '#';//#与原字符交替赋值
        s2[k++] = s1[i];
    }
    s2[k++] = '#';//最后一个也赋值为#
    s2[k] = 0;//结尾
    lens = k;// 扩展串长度
}
void manacher()//马拉车算法
{
    int id,mx=0;//id为中心位置  mx最大范围的右端 
    for(int i=0;i<lens;i++)//遍历一遍扩展串
    {
        if (mx > i) len[i] = min(mx - i, len[id * 2 - i]);
        else len[i] = 1;
        while (s2[i - len[i]] == s2[i + len[i]]) len[i]++;//如果两端相等就继续判断
        if (mx < len[i] + i)//如果最右端的值大于mx  更新mx
        {
            mx = len[i] + i;//更新mx的值
            id = i;//更新中间点的下标
            maxx = max(maxx, len[i]);//判断是否更新最大值
        }
    }
}

int main()
{
    cin >> s1;
    gets2();
    manacher();
    cout << maxx - 1 << endl;
    return 0;
}