The idea is to compute the fingerprints of the first k characters of the string, and fingerprints of the first k characters reversed. Then find the largest k where the fingerprint and reversed fingerprint of the first k characters are the same. Of course you verify s.substr(0, k) is a palindrome (it's likely to be) and continue finding if it's not.

The key is that fingerprints can be computed in O(n) time.

```
class Solution {
public:
static const int BASE = 19;
string shortestPalindrome(string s) {
int n = s.size();
if (n == 0) {
return "";
}
int fp[n];
int fp_r[n];
fp_r[0] = fp[0] = static_cast<int>(s[0]);
int mul = BASE;
for (int i = 1; i < n; ++i) {
// it's ok to overflow.
int tmp = static_cast<int>(s[i]);
fp[i] = fp[i - 1] * BASE + tmp;
fp_r[i] = fp_r[i - 1] + tmp * mul;
mul *= BASE;
}
int i = n - 1;
while (i) {
if (fp[i] == fp_r[i] && verify(s, i)) {
break;
}
i--;
}
return string(s.rbegin(), s.rend()) + s.substr(i + 1, n - i - 1);
}
bool verify(const string& s, int idx) {
for (int i = 0, j = idx; i < j; ++i, --j) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
};
```