算法一：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; } };