程序代码：

#include <iostream>
#include <vector>
using namespace std;

class Manacher
{
    public:
        string manach(const string &s) const;
};
string Manacher::manach(const string &s) const
{
    if(s.length()<0)
        return "";
    
    string t("$#");
    for(auto it=s.cbegin();it!=s.cend();++it)
    {
        t+=(*it);
        t+="#";
    }
    vector<int> a(t.length(),0);
    
    int Max_r=0,id=0,res=0,res_len=0;
    for(int i=1;i<t.length();++i)
    {
        /*a.at(i)=Max_r>i?min(a.at(2*id-i),Max_r-i):1;    
        while(t.at(i+a.at(i))==t.at(i-a.at(i)))
            ++a.at(i);*/ //这样写就会报错，说访问越界 
        
        a[i]=Max_r>i?min(a[2*id-i],Max_r-i):1;//这样写没问题 
        while(t[i+a[i]]==t[i-a[i]])
            ++a[i];
            
        if(Max_r<i+a.at(i))
        {
            id=i;
            Max_r=i+a.at(i);
        }
        
        if(res<a.at(i))
        {
            res=i;
            res_len=a.at(i);
        }
    }
    return s.substr((res-res_len)/2,res_len-1);
}
int main()
{
    string s1("1221");
    Manacher m;
    cout<<m.manach(s1)<<endl;
    return 0;
}