算法一：Manacher

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
const int N = int(2e5) + 9;
char s[N]; int r[N]; int n;

class Solution {
public:
    string shortestPalindrome(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;
        }
    
        int rn = 0x3f3f3f3f; DWN(i,n,1) if (r[i] == i){
            rn = nn-i+1;
            break;
        }
        
        string rr = ss; reverse(rr.begin(), rr.end());
        return rr.substr(0, rn) + ss;
    }
};

算法二：KMP

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
const int N = int(2e5) + 9;
int pi[N]; 

class Solution {
public:
    string shortestPalindrome(string ss) {
        string rr = ss; int nn = ss.size();
        reverse(rr.begin(), rr.end());
        string s = ss + '$' + rr;
        int n = s.size(); for (int i = 1, j = pi[0] = -1; i < n; ++i){
            while (j >= 0 && s[i] != s[j+1]) j = pi[j];
            if (s[i] == s[j+1]) ++j;
            pi[i] = j;
        }
        return rr.substr(0, nn-1-pi[n-1]) + ss;
    }
};

Posted by xiaodao
Category: LeetCode