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

Solution:

Method 1:

1. O(n^2)
2. index start from the end to the second character, check if the substring(0,index) is palindrome
   1. if so, add the reverse of the rest part to the beginning of the string
3. didn't pass time limited test

public String shortestPalindrome(String s) {
       if(s == null || s.length() <= 1){
            return s;
        }    
        int len = s.length();
        StringBuilder sb = new StringBuilder();

        for(int i = len; i >= 1; i--){
            if(isPalindrome(s.substring(0,i))){
                sb.append(s.substring(i,len)).reverse();
                break;
            }
        }
        if(sb == null){
           sb.append(s.substring(1,len)).reverse();
        }
        return sb.append(s).toString();
    }

    public boolean isPalindrome(String s){
        if(s.length() == 1){
            return true;
        }
        for(int i = 0; i < s.length() / 2; i++){
            if(s.charAt(i) != s.charAt(s.length() -1 -i)){
                return false;
            }
        }
        return true;
}

Method 2:

1. KMP: http://blog.csdn.net/v\_july\_v/article/details/7041827
2. create a new tmp string: s + # + s.reverse()
   1. find the longest palindrome ----> find the state function value of the last character in the tmp string
   2. state function is the next[i] in KMP, which tracks how many prefix and suffix characters are the same between start and the current position

       a b a b
      [0 0 1 2]
      

3. to implement the state function:

   1. index = 0, int i = 1 traverse to end of the tmp string

      1. if (char i == char index)
         1. index++ ---> to compare next;
         2. state[i] = state[i-1] + 1

      2. if (char i != char index){

         1. 当前的最长prefix == suffix不成立了，要找次长的prefix==suffix情况

            1. state[i-1] = j 表示：

               1. string 从0 到 j-1（prefix） == 从 i-1- j 到 i-1(both inclusive)（suffix） （此时是最大的可能相等长度），我们要做的是将匹配出来相同suffix的length 不断减小 ，直到state[i-1] = k （即找这个k的值）(or index == 0)， 使得string 从 0 到 k-1（prefix）== i-1-k 到 i-1（suffix） ---> how to find k -- using the state function of j-1

               2. example:

               3. ex： 
                  position： 0 1 2 3 4 5 6 7
                  strig：    a a a c d a a c   
                  state：    0 1 1 0 0 1 2
                  

   At position 7, index ---> 2, (substring(0,1) == substring(5,6)) (inclusive)---> charAt(2) != charAt(7) ----> index move to state[1] = 1, (substring(0,0) == substring(1,1) == substring(6,6))----> only needs to check if charAt(7) == charAt(1)

    public String shortestPalindrome(String s) {
        String tmp = s + "#" + new StringBuilder(s).reverse().toString();
        int[] state = new int[tmp.length()];
        int index = 0;

        for(int i = 1; i < state.length; i++){
            if(tmp.charAt(index) == tmp.charAt(i)){
                state[i] = state[i-1] + 1;
                index++;
            }else{
                index = state[i-1];

                while(index > 0 && tmp.charAt(index) != tmp.charAt(i)){
                    index = state[index-1];
                }

                if(tmp.charAt(index) == tmp.charAt(i)){
                    index++;
                }

                state[i] = index;
            }
        }

        StringBuilder sb = new StringBuilder(s.substring(state[tmp.length() - 1])).reverse();
        sb.append(s);
        return sb.toString();

    }

Reference:

https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation/2

https://segmentfault.com/a/1190000003059361