# 8-line O(n) method using Rabin-Karp rolling hash

• 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.

Java Code:

``````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.

Java Code:

``````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();
}
``````

• Can you explain hash1 and hash2? How is hash2 becoming equal to the hash1 on a palindrome. I can't understand the logic used to calculate these hashes

• Consider a decimal example. Say we are given a number `7134`. If we read it from left to right, we get 7134. And 4317 if we read it from right to left.

`hash1` is the left--to-right fashion:

• `hash1` = 0
• `hash1` = 0 * 10 + 7 = 7
• `hash1` = 7 * 10 + 1 = 71
• `hash1` = 71 * 10 + 3 = 713
• `hash1` = 713 * 10 + 4 = 7134

`hash2` is the right-to-left fashion:

• `hash2` = 0
• `hash2` = 0 + 7 * 1 = 7
• `hash2` = 7 + 1 * 10 = 17
• `hash2` = 17 + 3 * 100 = 317
• `hash2` = 317 + 4 * 1000 = 4317

A palindrome must be read the same from left to right and from right to left. So in this case, `7134` is not a palindrome.

Above is an example for the decimal case, and for rolling hashing, the only differences are:

1. Base is not 10, but any constant >= 26.
2. `hash1` and `hash2` are not the exact value, but the exact value modulo a big prime. (Since the exact value is too large to fit in a 32-bit integer.)

As you may notice, the rolling hash function is not an injection, which means that two different strings may share the same hash code.
(This is also commonly called a conflict.) But in real, it is very difficult to trigger many conflicts (sometimes not even a single one) unless there are sufficiently many strings given.
Therefore, if `hash1` is not equal to `hash2` for some string, then definitely it is not a palindrome. On the other hand, if they are equal, it means the string is a palindrome with extreme high probability.

• with extreme high probability.

But it is still not 100% probability, right? So you still need to do spurious test for the correctness of the algorithm, right?

• Just played with your code, If there is no MOD, it still past all tests.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.