class Solution {
    public String shortestPalindrome(String s) {
       String rev = new StringBuffer(s).reverse().toString();
       int n = s.length();
       int i = 0;
       //dcba abcd
        for(i=0;i<n;i++)
        {
            if(s.substring(0,n-i).equals(rev.substring(i,n)))
                break;
        }
        return new StringBuffer(s.substring(n-i)).reverse().toString()+s;
    }
}

解法二：kmp算法求解

如果熟悉了 KMP 算法，就非常简单了。

再回想一下解法一，倒置字符串的思路，依次比较对应子串。

abbacd

原s: abbacd, 长度记为 n 逆r: dcabba, 长度记为 n

我们把两个字符串写在一起 abbacd dcabba

判断 abbacd 和 dcabba 是否相等
判断 abbac 和 cabba 是否相等
判断 abba 和 abba 是否相等

如果我们把 abbacd dcabba看成一个字符串，中间加上一个分隔符 #，abbacd#dcabba。

回味一下上边的三条判断，判断 XXX 和 XXX 是否相等，按列看一下。

左半部分 abbacd，abbac , abba 其实就是 abbacd#dcabba 的一些前缀。

右半部分dcabba，cabba，abba 其实就是 abbacd#dcabba 的一些后缀。

寻找前缀和后缀相等。

想一想 KMP 算法，这不就是 next 数组做的事情吗。

而我们中间加了分隔符，也就保证了前缀和后缀相等时，前缀一定在 abbacd 中。

换句话说，我们如果求出了 abbacd#dcabba 的 next 数组，因为我们构造的字符串后缀就是原字符串的倒置，前缀后缀相等时，也就意味着当前前缀是一个回文串，而 next 数组是寻求最长的前缀，我们也就找到了开头开始的最长回文串。

因为 next 数组的含义并不统一，但 KMP 算法本质上都是一样的，所以下边的代码仅供参考。

class Solution {
    public String shortestPalindrome(String s) {
        //kmp算法求解
        //例如abbacd
        //构造abbacd#dcabba 
        String temp = s+'#'+new StringBuffer(s).reverse().toString();
        int result = getNext(temp);
        return new StringBuffer(s.substring(result+1)).reverse()+s;
       
    }
    //返回next数组的最后一个值 返回的是3
     public int getNext(String s)
    {
        char a[] = s.toCharArray();
        int []next = new int[a.length];
        next[0] = -1;
        int i = -1;
        int j = 0;
        while(j<a.length-1)
        {
            if(i==-1 || a[i]==a[j])
            {
                i++;j++;
                next[j] = i;
            }
            else
                i = next[i];
        }
        return next[a.length-1];        
    }
}