Shortest Palindrome

//KMP Knuth Morris Pratt https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
public String shortestPalindrome(String s) {
    String temp = s + "#" + new StringBuilder(s).reverse().toString();
    int[] table = getTable(temp);
    
    //get the maximum palin part in s starts from 0
    return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}

public int[] getTable(String s){
    //get lookup table
    int[] table = new int[s.length()];
    
    //pointer that points to matched char in prefix part
    
    int index = 0;
    //skip index 0, we will not match a string with itself
    for(int i = 1; i < s.length(); i++){
        if(s.charAt(index) == s.charAt(i)){
            //we can extend match in prefix and postfix
            table[i] = table[i-1] + 1;
            index ++;
        }else{
            //match failed, we try to match a shorter substring
            
            //by assigning index to table[i-1], we will shorten the match string length, and jump to the 
            //prefix part that we used to match postfix ended at i - 1
            index = table[i-1];
            
            while(index > 0 && s.charAt(index) != s.charAt(i)){
                //we will try to shorten the match string length until we revert to the beginning of match (index 1)
                index = table[index-1];
            }
            
            //when we are here may either found a match char or we reach the boundary and still no luck
            //so we need check char match
            if(s.charAt(index) == s.charAt(i)){
                //if match, then extend one char 
                index ++ ;
            }
            
            table[i] = index;
        }
        
    }
    
    return table;
}

//Rabin Karp Rolling Hash Solution https://en.wikipedia.org/wiki/Rolling_hash
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();
}

//https://leetcode.com/problems/shortest-palindrome/solutions/4588959/expanding-window-from-center-48ms/
const shortestPalindrome = (()=> {
    "use strict";

    const shortestPalindrome = s => { // abcd --> dcbabcd
        if (s.length <= 1) return s;
        const mid = Math.ceil(s.length/2) - 1;

        for (let i = mid; i !== -1; ) {
            const [l, length] = getLeftPalLength(s, i, i === mid);
            if (length === -1) {
                i = l;
            } else if (l === -1) {
                return prependTail(s, length);
            } else {
                i--; // xabac
            }
        }
    };

/** 
 * Length of the palindrome from index 0.
 * If no such palindrome is found, return 0.
 */ const getLeftPalLength = (s, i, isMiddle) => {
        let [l, r] = sameCharOutsideBounds(s, i, isMiddle);
        if (r !== -1) { //// xabac
            while (l !== -1 && s[l] === s[r]) {
                l--;
                r++;
            }
        }
        return [l, r];
    };
    
/** 
 * Returns the boundaries outside the center contiguous 
 * characters or -1 if `s` cannot form a left-justified 
 * palindrome.
 * 
 * We return early with a negative `r` value when contiguous 
 * chars are offset to the right of the string's middle, as — 
 *    abc[ddd]c  
 * — or —
 *    bcxxc
 * where number of chars after `r` < number of chars before `l`.
 */ const sameCharOutsideBounds = (s, i, isMiddle) => {
        const palChar = s[i];
        let l = i;
        let r = i;
        while (s[--l] === palChar);
        if (isMiddle) {
            const tooFar = (i - l - 1) + (s.length - 1) % 2;
            for (let dr = 0; s[r] === palChar; dr++, r++) {
                if (dr === tooFar) return [l, -1];
            }
        } else r++;
        return [l, r];
    };

    const prependTail = (s, length) => {
        if (length === s.length) return s;
        return s.slice(length).split("").reverse().join("") + s;
    };

    return shortestPalindrome;
})();