```
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
int[] hash = new int[n + 1], exp = new int[n + 1];
exp[0] = 1;
int mul = 10000007;
for (int i = n - 1; i >= 0; i--)
hash[i] = hash[i + 1] * mul + s.charAt(i);
for (int i = 1; i <= n; i++)
exp[i] = exp[i - 1] * mul;
int maxLen = 0;
int hashl = 0;
for (int i = 0; i < n; i++) {
hashl = hashl * mul + s.charAt(i);
int hashr = hash[0] - hash[i + 1] * exp[i + 1];
if (hashl == hashr)
maxLen = i + 1;
}
String rev = new StringBuilder(s).reverse().toString();
return maxLen == 0 ? "" : rev + s.substring(maxLen);
}
}
```