Manacher
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
const int N = int(2e3) + 9;
char s[N]; int r[N]; int n;
class Solution {
public:
string longestPalindrome(string ss) {
int nn = ss.size();
n = 2*nn+2; s[0] = '$'; REP(i, nn) s[i*2+1]='.',s[i*2+2]=ss[i];s[n-1]='.'; s[n] = 0;
int mx=0,mi=0;FOR(i,1,n){
for (r[i]=mx>i?min(r[2*mi-i],mx-i):1;s[i+r[i]]==s[i-r[i]];++r[i]);
if (i+r[i]>mx)mx=i+r[i],mi=i;
}
mx=0;FOR(i,1,n)if(r[i]>mx)mx=r[i],mi=i;--mx; string z;
for(int i=mi-mx+1;i<mi+mx;i+=2) z += s[i];
return z;
}
};
