Leetcode 214 Shortest Palindrome

This question is a variety of question 5 in leetcode.

The first solution is a straight forward solution that copy the a substring from the end to the front. The length of substring increase from 1 to n/2.
After every copy operation, call a check function isPali() to check whether current is a Pali string.

The java code for solution 1 is :

  
public class Solution {
    public String shortestPalindrome(String s) {

        // the simple method is o(n2), to have a better solution
        // need to use manchester or KMP
        //here we implmenet Manchester algorithm, it can find the longest 

       String str=s;int len=s.length();
        int index=0;
        while(!isPalinadrome(str))
        {  StringBuilder sb=new StringBuilder(s);
           sb.reverse();
           String sub=s.substring(len-index-1,len);
           sb.append(sub);
            str=sb.toString();
            index++;
        }
        return str;

｝
 public boolean isPalinadrome(String s)
    {
          int lo=0; int hi=s.length()-1;
            while (lo < hi) {
                if (s.charAt(lo) != s.charAt(hi)) {
                    return false;
                }
                lo++;
                hi--;
            }
            return true;
        }

The second solution is to use Manacher algorithm, for more details it can be checked at:
http://www.felix021.com/blog/read.php?2040

public class Solution {
    public String shortestPalindrome(String s) {
      
        if(s.length()<2) return s;
        String str=buildNewString(s);
        int [] p=new int [str.length()]; // the array to store largest pali at position i
        int idx=0;   //center of max pali
        int max=1;   //edge of max pali
        int res_max=1;
        int res_idx=0;
        for(int i=1;i<str.length();i++)
        {
          if(max>i)
          p[i]=Math.min(max-i,p[2*idx-i]);
          else p[i]=1;

          //
          while(i-p[i]>=0&&i+p[i]max)
          {max=i+p[i];
              idx=i;
          }
         if(max-idx>res_max-res_idx&&2*idx-max+1==0)
          {
              res_max=max;
              res_idx=idx;
          }
        }
        
        StringBuilder result= new StringBuilder();
        for(char c:str.substring(res_max).toCharArray()){
            if(c!='#')
                result.append(c);
        }
        return result.reverse().append(s).toString();
        
    }
    
    // adding '#' between every character, avoiding odd number problem.

    public String buildNewString(String s)
    { StringBuilder sb=new StringBuilder();
      sb.append('#');
      for(int i=0; i<s.length();i++)
      {
          sb.append(s.charAt(i));
          sb.append('#');
      }
      return sb.toString();
    }
}