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

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