This problem is indeed computing the longest palindromic prefix of a string s.

A naive approach would be computing all the prefixes of s and its reverse, and

then finding the longest pair of prefixes that are equal.

Unfortunately, this method requires quadratic time and space since

the length sum of all prefixes is 1+2+...+|s| = Θ(|s|^2).

Via the help of the Rolling Hash method, the above process can be optimized down to linear time.

For more details, you can visit here and here.

```
public String shortestPalindrome(String s) {
int n = s.length(), pos = -1;
long B = 29, MOD = 1000000007, POW = 1, hash1 = 0, hash2 = 0;
for (int i = 0; i < n; i++, POW = POW * B % MOD) {
hash1 = (hash1 * B + s.charAt(i) - 'a' + 1) % MOD;
hash2 = (hash2 + (s.charAt(i) - 'a' + 1) * POW) % MOD;
if (hash1 == hash2) pos = i;
}
return new StringBuilder().append(s.substring(pos + 1, n)).reverse().append(s).toString();
}
```

Below is another solution by using KMP. For details, please refer to here.

```
public String shortestPalindrome(String s) {
String concat = new StringBuilder(s).append('.').append(new StringBuffer(s).reverse()).toString();
int[] next = new int[concat.length()];
for (int i = 0, ptr = -1; i < next.length; ptr = next[i], i++) {
while (ptr > -1 && concat.charAt(ptr + 1) != concat.charAt(i)) ptr = next[ptr];
next[i] = i > 0 && concat.charAt(ptr + 1) == concat.charAt(i) ? ptr + 1 : -1;
}
return new StringBuilder(s.substring(next[next.length - 1] + 1, s.length())).reverse().append(s).toString();
}
```