CodeCollection2018
8/29/2019 - 11:45 AM

最短回文子串

给定某个字符串，然后要求可以在该字符串之前加一些字符来构成整体性的回文字符串。求最短的回文字符串。 实际最差的情况就是把给定的字符串反转过来然后拼接在原字符串前面来生成，但不是最短的。但是可以发现结果字符串是回文字符串而且其对称中心一定在原字符串某个位置，所以源字符串头部应该找最长的回文字符串，该题就是寻找原字符串最长的头部回文字符串，实际就想找到原字符串中某个分界点使得其前面的字符串和后面相同长度的字符串是镜像关系的。 一种十分巧妙的方法是将源字符串s反转得到reverse(s)然后拼接在s后面形成s+"#"+reverse(s)，然后将其作为模式串应用KMP算法计算其next数组，因为next数组中每一个数字代表不包括该字符在内的前面所有字符组成的字符串最大相同前后缀长度，这种拼接之后的结果用KMP算法，实际相当于假设原字符串是ABC其中A和B应该是镜像关系的，也就是分界点在A和B之间，而拼接之后的字符串是ABC#CBA，此时如果A恰好等于B，而B恰好等于~A。

kmp
content_copyfile_download
//kmp
public String shortestPalindrome(String s){
    String r = new StringBuilder(s).reverse().toString();
    String t = s+"#"+r;
    int[] next = new int[t.length()];
    for(int i = 1; i < t.length() ; i++){
        int j= next[i-1];//next[i-1]就是第i个字符能够匹配的最长的前缀的长度
        while(j >0 && t.charAt(i)!=t.charAt(j)) j=next[j-1];//逐渐缩小匹配范围
        j += (t.charAt(i)==t.charAt(j))?1:0;//最终还是要看最小范围中j和i匹配不匹配
        next[i]=j;//next[j]表示包含j对应的字符在内的最长相同前后缀
    }
    return r.substring(0,s.length()-next[t.length()-1])+s;
}