I use hash to check whether it is palindrome.

```
string shortestPalindrome(string s) {
typedef unsigned long long ull;
const ull B = (ull)(1e9+7);
int size = s.size();
ull l = 0, r = 0;
vector<ull> Pow(size+1, 1);
for(int i=1; i<=size; i++) Pow[i] = Pow[i-1] * B;
int M = 0;
for(int i=0; i<size; i++){
l = l*B + s[i];
r = r + s[i] * Pow[i];
if(l == r){
M = i+1;
}
}
int res = size-M;
string p = s;
cout<<res<<endl;
for(int j=res-1; j>=0; j--){
p = s[size-1-j]+p;
}
return p;
}
```