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


  • 4
    L

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

  • 0
    W

    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


  • 2
    L

    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.


  • 0
    S

    @lixx2100 said in 8-line O(n) method using Rabin-Karp rolling hash:

    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?


  • 0
    S

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


Log in to reply
 

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