Shortest Palindrome

用Java暴力是可以過(guò)的，思路也很簡(jiǎn)單：補(bǔ)充完成之后的回文串中心必定在原字符串中，所以原字符串以第一個(gè)字符為起點(diǎn)必然存在至少一個(gè)回文串（長(zhǎng)度可以為1），那么任務(wù)就變?yōu)檎业皆址幸缘谝粋€(gè)字符為起點(diǎn)最長(zhǎng)的回文串，找到之后剩下的工作就是把剩余部分的翻轉(zhuǎn)補(bǔ)充到原字符串頭部即可。

這樣代碼邏輯就很簡(jiǎn)單，就是從原字符串的頭部開(kāi)始截取子串，長(zhǎng)度遞減，直到獲取到第一個(gè)是回文串的子串，此時(shí)就找到了需要截?cái)嗟牟糠?，從該位置開(kāi)始到原字符串末尾就是需要截取并翻轉(zhuǎn)拼接的部分。算法復(fù)雜度是O(n^2)。

實(shí)現(xiàn)代碼：

public class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) return s;
        int len = s.length(), tail = len;
        StringBuilder builder = new StringBuilder();
        while (1 < tail) {
            if (isPalindrome(s.substring(0, tail))) {
                builder = builder.append(s.substring(tail, len)).reverse();
                break;
            }
            tail--;
        }
        if (builder.length() == 0) {
            builder = builder.append(s.substring(tail, len)).reverse();
        }
        return builder.append(s).toString();
    }

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

LeetCode做多了也就知道O(n^2)的算法必然有改進(jìn)版，自己思考了下沒(méi)有悟出來(lái)，就參考了這篇文章：[LeetCode] Shortest Palindrome 最短回文串。

其實(shí)思路也很簡(jiǎn)單：

1. 求字符串s的翻轉(zhuǎn)s_rev
2. 將兩個(gè)字符串進(jìn)行拼接：{s}#{s_rev}
3. 找出新字符串中最長(zhǎng)公共前綴后綴長(zhǎng)度comLen
4. s_rev.substring(0, s.length() - comLen)就是在原字符串頭部插入的子串部分

舉個(gè)例子：

對(duì)于字符串s：babcd，先求rev_s：dcbaba，拼接之后：babcd#dcbaba。上文已經(jīng)解釋過(guò)，s的前綴必然是一個(gè)回文串（長(zhǎng)度可能為1），任務(wù)就是求這個(gè)回文串的最長(zhǎng)長(zhǎng)度，因此拼接之后的{s}#{s_rev}必然有公共前綴后綴，任務(wù)就是求這個(gè)公共前綴后綴的最長(zhǎng)長(zhǎng)度，那么這個(gè)時(shí)候就需要祭出KMP算法了。有了解的同學(xué)，估計(jì)一看就看出這個(gè)就是求KMP里的next數(shù)組。由于之前學(xué)KMP的時(shí)候也只學(xué)了個(gè)一知半解，所以這次又重新學(xué)習(xí)了下從頭到尾徹底理解KMP（2014年8月22日版），這下對(duì)KMP又有更好的理解了。

詳細(xì)的KMP算法上面提到的文章里講的非常詳細(xì)，就不從頭說(shuō)了。這里講一講我之前一直困惑現(xiàn)在理解了的點(diǎn)。

對(duì)于KMP算法，核心的地方就是求next數(shù)組，而求next數(shù)組中比較難理解的地方就是當(dāng)當(dāng)前位置的字符和目標(biāo)字符不匹配的時(shí)候。對(duì)于字符串s，已經(jīng)有p[0]到p[i-1]，且p[i-1]=j，求p[i]（p即next數(shù)組，其中p[k]表示從0到k位置為止公共前綴后綴的長(zhǎng)度，例如：abacaba，公共前綴后綴長(zhǎng)度是3，當(dāng)p[k]=m則表示s.substring(0,m)和s.substring(k-m+1,k+1)是相等的）：

1. 若s[i]=s[j]，也就是當(dāng)前字符延續(xù)了之前的公共前綴后綴，那么p[i]=p[i-1]+1即可
2. 若s[i]!=s[j]，即s.substring(0,j)和s.substring(i-j+1,i+1)是不匹配的，但是仍然可能存在s.substring(0,x)和s.substring(i-x+1,i+1)，這一點(diǎn)就是我以前最不能理解的地方，這次結(jié)題的經(jīng)歷加深了我這部分的理解。

到目前位置，期望i位置的最長(zhǎng)公共前綴后綴為j+1的期望已經(jīng)失敗，那我是否可以期望下縮短長(zhǎng)度之后能有匹配的公共前綴后綴呢？答案是肯定的，因?yàn)閷?duì)于位置i-1來(lái)說(shuō)，其實(shí)是可能存在多個(gè)公共前綴后綴的，只是p[i-1]只記錄其中最長(zhǎng)的，那么次長(zhǎng)的是多少呢，答案就在p[j-1]里。對(duì)于位置i-1來(lái)說(shuō)，已知0到j-1的子串和i-j+1到i-1子串是相等的，而對(duì)于位置j-1來(lái)說(shuō)，從0到p[j-1]-1的子串和從j-p[j-1]到j-1的子串是相同的，更進(jìn)一步和i-p[j-1]到i-1的子串也是相同的，那如果現(xiàn)在比較一下i和p[j-1]是否相等同樣可以求出最長(zhǎng)公共前綴后綴的值（因?yàn)?code>p中記錄是到每個(gè)位置為止的最長(zhǎng)公共前綴后綴，所以這樣每次遞推下去每次得到都是當(dāng)前可能的最長(zhǎng)公共前綴后綴）。

梳理一下，就是對(duì)于位置i-1而言，公共前綴后綴的長(zhǎng)度依次為：p[i-1],p[p[i-1]-1],p[p[p[i-1]-1]-1],……。在此基礎(chǔ)上，對(duì)于位置i而言，只要比對(duì)某幾個(gè)特定的位置，看s[i]是否能符合條件（即是否和當(dāng)前公共前綴后綴后的第一個(gè)字符相等）就能求得p[i]的值。當(dāng)然，如果比對(duì)某個(gè)位置的時(shí)候p[x]已經(jīng)為0，那么就可以馬上結(jié)束比較跳出循環(huán)，然后只要和首字母比對(duì)下就行了（因?yàn)檫@種情況說(shuō)明可能的公共前綴后綴都已經(jīng)被比對(duì)完了，s[i]依然不符合條件，那么只能從頭開(kāi)始了）。

應(yīng)用了KMP之后的實(shí)現(xiàn)代碼：

public class Solution {
    public String shortestPalindrome(String s) {
        StringBuilder builder = new StringBuilder(s);
        return builder.reverse().substring(0, s.length() - getCommonLength(s)) + s;
    }

    private int getCommonLength(String str) {
        StringBuilder builder = new StringBuilder(str);
        String rev = new StringBuilder(str).reverse().toString();
        builder.append("#").append(rev);
        int[] p = new int[builder.length()];
        for (int i = 1; i < p.length; i++) {
            int j = p[i - 1];
            while (j > 0 && builder.charAt(i) != builder.charAt(j)) j = p[j - 1];
            p[i] = j == 0 ? (builder.charAt(i) == builder.charAt(0) ? 1 : 0) : j + 1;
        }
        return p[p.length - 1];
    }
}