29.标准马拉车

class Solution {
    int f[5005];
public:
    string longestPalindrome(string s) {
        string t="!#";
        for(auto c:s){
            t+=c;
            t+='#';
        }
        t+='$';
        int rMax=0,iMax=0,resId=0,resLen=0;
        int n=t.size();
        for(int i=1;i<n;i++){
            f[i]=(i<=rMax)?min(rMax-i+1,f[2*iMax-i]):1;
            while(t[i+f[i]]==t[i-f[i]])++f[i];
            if(i+f[i]-1>rMax){
                rMax=i+f[i]-1;
                iMax=i;
            }
            if(f[i]>resLen){
                resLen=f[i];
                resId=i;
            }
        }
       return s.substr((resId-resLen)>>1,resLen-1);
    }
};