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;
    }
};

Posted by xiaodao
Category: LeetCode