严格复杂度O（N）            

　　step1:预处理，将奇偶变为奇数。

 对于一个串str长度为n，有n-1个空格，首位有两个，对这些空处理，长度变成2n+1。

可以加str中不存在的东西，比如#。

　　step2: 构造数组p[n]

数组p[i]来记录字符串s[i]最长回文串向左向右扩张p[i]长度的最大值。

（全都是奇数）

（注意：必须构造成奇数序列才可以向两边扩充，得到p[i]数组，举个例子）

string :1221

p[i]     :1111

未发现回文

马士兵教育左神：https://www.bilibili.com/video/BV1YL4y1v7Hy?p=42

探寻时间复杂度

失败：

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

成功

把扩充和i变大绑在一起了

非左程云版马拉车

#include <vector>
#include <iostream>
#include <string>

using namespace std;

string Mannacher(string s){
    //插入"#"
    string t="$#";
    for(int i=0;i<s.size();++i)
    {
        t+=s[i];
        t+="#";
    }
    
    vector<int> p(t.size(),0);
    //mx表示某个回文串延伸在最右端半径的下标，id表示这个回文子串最中间位置下标
    //resLen表示对应在s中的最大子回文串的半径，resCenter表示最大子回文串的中间位置
    int mx=0,id=0,resLen=0,resCenter=0;

     //建立p数组
    for(int i=1;i<t.size();++i){
        p[i]=mx>i?min(p[2*id-i],mx-i):1;

        //遇到三种特殊的情况，需要利用中心扩展法
        while(t[i+p[i]]==t[i-p[i]])++p[i];

        //半径下标i+p[i]超过边界mx，需要更新
        if(mx<i+p[i]){
            mx=i+p[i];
            id=i;
        }

        //更新最大回文子串的信息，半径及中间位置
        if(resLen<p[i]){
            resLen=p[i];
            resCenter=i;
        }
    }

    //最长回文子串长度为半径-1，起始位置为中间位置减去半径再除以2
    return s.substr((resCenter-resLen)/2,resLen-1);
}

int main(){
    cout<<Mannacher("12212")<<endl;
    cout<<Mannacher("122122")<<endl;
    cout<<Mannacher("noon")<<endl;
    return 0;
}

https://windliang.wang/2019/06/24/%E4%B8%80%E6%96%87%E8%AE%A9%E4%BD%A0%E5%BD%BB%E5%BA%95%E6%98%8E%E7%99%BD%E9%A9%AC%E6%8B%89%E8%BD%A6%E7%AE%97%E6%B3%95/

https://www.cnblogs.com/transmigration-zhou/p/13471829.html