package com.fishercoder.solutions;

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


 */
public class _214 {

    /**credit: https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation*/
    /**TODO: read it explanation and understand KMP completely.*/
    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;
    }

}

@@ -59,16 +59,17 @@
 indrome%0A
+%0A
  Given a
@@ -341,18 +341,16 @@
 babcd%22.%0A
-%0A%0A
  */%0Apubl
@@ -366,16 +366,56 @@
 _214 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     /**c
@@ -519,19 +519,35 @@
 n*/%0A    
-/**
+    /**%0A         * 
 TODO: re
@@ -594,23 +594,37 @@
 pletely.
-*/%0A
+%0A         */%0A   
     
+ 
 public S
@@ -652,32 +652,36 @@
 ome(String s) %7B%0A
+    
         String t
@@ -739,32 +739,36 @@
 ring();%0A        
+  
+  
 int%5B%5D table = ge
@@ -781,16 +781,20 @@
 (temp);%0A
+    
         
@@ -845,24 +845,28 @@
 m 0%0A        
+ 
+   
 return new S
@@ -942,27 +942,35 @@
 () + s;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     public i
@@ -999,24 +999,28 @@
 ) %7B%0A        
+   
+ 
 //get lookup
@@ -1026,16 +1026,20 @@
 p table%0A
+    
         
@@ -1082,16 +1082,20 @@
         
+  
+  
 //pointe
@@ -1139,16 +1139,20 @@
 ix part%0A
+    
         
@@ -1174,16 +1174,20 @@
         
+    
 //skip i
@@ -1241,16 +1241,20 @@
         
+   
+ 
 for (int
@@ -1288,32 +1288,36 @@
 ) %7B%0A            
+    
 if (s.charAt(ind
@@ -1350,24 +1350,28 @@
             
+  
+  
 //we can ext
@@ -1410,32 +1410,36 @@
                 
+    
 table%5Bi%5D = table
@@ -1459,32 +1459,36 @@
                 
+ 
+   
 index++;%0A       
@@ -1472,32 +1472,36 @@
        index++;%0A
+    
             %7D el
@@ -1521,16 +1521,20 @@
         
+    
 //match 
@@ -1594,16 +1594,20 @@
         
+   
+ 
 //by ass
@@ -1707,16 +1707,20 @@
         
+    
 //prefix
@@ -1778,32 +1778,36 @@
                 
+  
+  
 index = table%5Bi 
@@ -1809,24 +1809,28 @@
 le%5Bi - 1%5D;%0A%0A
+    
             
@@ -1879,32 +1879,36 @@
  s.charAt(i)) %7B%0A
+    
                 
@@ -2024,32 +2024,36 @@
                 
+   
+ 
 index = table%5Bin
@@ -2070,35 +2070,43 @@
                 
-%7D%0A%0A
+    %7D%0A%0A    
                 
@@ -2213,16 +2213,20 @@
         
+    
 //so we 
@@ -2255,32 +2255,36 @@
                 
+ 
+   
 if (s.charAt(ind
@@ -2297,32 +2297,36 @@
  s.charAt(i)) %7B%0A
+    
                 
@@ -2374,32 +2374,36 @@
                 
+    
 index++;%0A       
@@ -2403,34 +2403,42 @@
                 
+  
-%7D%0A
+  %7D%0A    
                 
@@ -2459,34 +2459,42 @@
 ex;%0A            
-%7D%0A
+    %7D%0A    
         %7D%0A      
@@ -2491,24 +2491,28 @@
   %7D%0A        
+    
 return table
@@ -2517,13 +2517,22 @@
 le;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 214