leetcode 214 Shortest Palindrome

lc214 Shortest Palindrome

可以將問題轉化成找到原字符串的最長palindrome子串（注意，子串必須以s[0]為起始）

例如：sdserf

sds為最長palindrome子串

只需要將sds之后的子串翻轉一下，補充到原字符串之前即可

fre + sdserf

?

那么如何找到最長palindrome子串呢？

使用KMP

s + “@” + reverse(s)

@的目的是保證s的每一位都與其翻轉后相應位置對應，避免由于字符串長度為奇數或為偶數而產生的差別

與原版KMP算法稍微有一些區別，原版kmp表的每一位kmp[i]表示s(0~i-1)不包含i，而這里的KMP表則應該包含i，為s(0~i)

除此之外，由于我們這里只需要求kmp表而不需要考慮模式串和主串的匹配，所以不需要將kmp[0]設為-1，而是直接設為0

具體KMP的算法原理可以參見：https://www.cnblogs.com/yjiyjige/p/3263858.html

class Solution {
    public String shortestPalindrome(String s) {
        String temp = s + "!" + new StringBuilder(s).reverse().toString();
        
        int[] KMP = kmp(temp);
        return new StringBuilder(s.substring(KMP[KMP.length-1])).reverse() + s;
        
    }
    private int[] kmp(String s){
        int k=0;
        int[] res = new int[s.length()];
        
        for(int i=1; i<s.length()-1; ){
            if(s.charAt(k) == s.charAt(i)){
                res[i] = ++k;
                i++;
            }else{
                if(k > 0){
                    k = res[k-1];
                }else{
                    i++;
                }
            }
        }
        return res;
    }
}

?