214. Shortest Palindrome

刷
July-14-2019
还是挺难的，又过了一遍KMP.

最直接的办法是楞做。
abcd = > bcd abcd
aacecaaa => a aacecaaa
说白了就是找到给定String里面longest palindrome prefix。
怎么找呢？ 最直观的做法就是左右同时往中间，扫到相遇说明本身就是plindrome。
失败的话，去掉右边最后一位， 重新扫，就是aacecaaa =>去掉最后一个A，继续扫 aacecaa然后发现满足。 这么做时间就爆炸了。

一个稍微好点的办法是

    public String shortestPalindrome(String s) {
        if (s.length() <= 1) return s;
        
        int l = 0;
     
        for (int r = s.length() - 1; r >= 0; r --) {
            if (s.charAt(r) == s.charAt(l)) {
                l ++;
            }
        }
        if (l == s.length()) return s;
        
        return new StringBuilder(s.substring(l)).reverse().toString() + shortestPalindrome(s.substring(0, l)) + s.substring(l);
    }
}

失败之后，继续，最后3个位置 0 - l - end来说，l-end肯定不符合规矩，需要翻转加到最前面，0-l不确定，只知道longest prefix palindrome肯定在这里面，所以继续recursively call。 其实这个也不好理解，我大概的理解是，每个LR的mismatch会让l最终到END的距离+1.

刚才说道KMP，

palindrome + something = S，我们要找的就是longest palindrome
assuming palindrome of S = S·
palindrome + something + something· + palindrome· = SS·
palindrome = palindrome·
这个问题变成了求SS·的最长 前缀=后缀，就是KMP的next[]干的事。
不同的一点是，KMP里的NEXT可以让前缀后缀有overlap，比如aaaaa的最长前缀=后缀是aaaa而不是aa
所以得保证我们generate KMP next[]的时候最长不能超过一半，有2个办法，一个是在SS`中间加个不存在与S中的字符，类似于S + "&" + S·这样每次OVERLAP都肯定会FAIL
另一个办法是每次到了超过一半的位置就reset J，比较难理解，得深刻想明白为什么NEXT要那样GENERATE出来才能理解。

class Solution {
    public String shortestPalindrome(String s) {
        if (s.length() <= 1) return s;
        
        int[] kmp = generateKmp(s + new StringBuilder(s).reverse().toString());
        
        int index = kmp[kmp.length - 1];

        return new StringBuilder(s.substring(index)).reverse().toString() + s;
        
    }
    
    public int[] generateKmp(String s) {
        if (s == null) return null;
        int[] res = new int[s.length()];
        
        int j = 0;
        for (int i = 1; i < s.length(); i ++) {
            if (i == s.length() / 2) j = 0;
            while (j != 0 && s.charAt(i) != s.charAt(j)) {
                j = res[j - 1];
            }
            
            if (s.charAt(i) == s.charAt(j)) {
                j ++;
            }
            
            res[i] = j;
        }
        return res;
    }
}