Leetcode - 214. Shortest Palindrome

214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Analysis:
  S#S' will make a valid palindrome. Key is to use KMP algo to find existing repeating part from the half, which is S
 ex1:   aa#aa
KMP: 01012  -> so we will have s.substring(2).reverse + s = '' + 'aa' = 'aa'
ex2:   bba#abb
KMP: 0100012 -> so we will have s.substring(1).reverse +  s = 'a.reverse' + 'bba' = abba

Complexity: O(N)

var shortestPalindrome = function(s) {
    if(s.length < 1){return s;}
    var pali = s+"#"+s.split("").reverse().join("");//s#s'
   //storing next entry pos for comparision
    var kmp = getKMP(pali);
    console.log(kmp)
    var length = kmp[kmp.length-1];
    return s.substring(length).split("").reverse().join("") + s;
};

function getKMP(s){
    var j = 0;
    var table = [];
    table[0] = 0;
    for(var i = 1; i < s.length; i++){
        while(s[i] !== s[j] && j > 0){
            j = table[j-1];
        }
        if(s[i] === s[j]){
            table[i] = j+1;
            j++;
        }else{
            table[i] = 0;
        }
    }
    return table;
}