# LeetCode 214. Shortest Palindrome

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