manacher

string manacher(string s){  //求字符串s的最长回文子串
    string t="$#";
    for(int i=0;i<s.size();i++){
        t+=s[i];
        t+="#"; //预处理字符串
    }
    vector<int> p(t.size(),0); //初始化回文半径数组
    int mx=0,id=0,resLen=0,resCenter=0;
    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];}
        if(mx<i+p[i]){
            mx=i+p[i];
            id=i;
        }
        if(resLen<p[i]){
            resLen=p[i];
            resCenter=i;
        }
    }
    return s.substr((resCenter-resLen)/2,resLen-1);

}