马拉车算法求解最长回文子串

Problem: 5. 最长回文子串

思路

马拉车算法解决最长回文子串问题

解题方法

参考这篇博客：https://segmentfault.com/a/1190000008484167

Code

class Solution {
    //马拉车算法
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        StringBuilder builder = new StringBuilder("^");
        for(int i=0; i<s.length(); i++){
            builder.append("#");
            builder.append(s.charAt(i));
        }
        builder.append("#$");

        //辅助数组，p[i]表示以i为中心的最长回文半径
        int n = builder.length();
        int[] p = new int[n];
        p[0] = 1; p[n-1] = 1; p[1] = 1; 

        int maxLen = 1;
        int id=0, mx=0,index=0;

        for(int j=2; j<n-1;j++){
            if(mx > j) {
                p[j] = Math.min(p[2 * id - j], mx-j);
            }else p[j] = 1;

            while(builder.charAt(j+p[j]) == builder.charAt(j-p[j])){
                p[j]++;
            }
            if(mx < p[j] + j){
                mx = p[j]+j;
                id = j;
            }
            if(maxLen < p[j] - 1){
                maxLen = p[j] - 1;
                index = j;
            }
        }
        int start = (index - maxLen) / 2;
        return s.substring(start,start+maxLen);
    }
}