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

1
class Solution {
2
    //马拉车算法
3
    public String longestPalindrome(String s) {
4
        if(s.length() <= 1) return s;
5
        StringBuilder builder = new StringBuilder("^");
6
        for(int i=0; i<s.length(); i++){
7
            builder.append("#");
8
            builder.append(s.charAt(i));
9
        }
10
        builder.append("#$");
11

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

17
        int maxLen = 1;
18
        int id=0, mx=0,index=0;
19

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

25
            while(builder.charAt(j+p[j]) == builder.charAt(j-p[j])){
26
                p[j]++;
27
            }
28
            if(mx < p[j] + j){
29
                mx = p[j]+j;
30
                id = j;
31
            }
32
            if(maxLen < p[j] - 1){
33
                maxLen = p[j] - 1;
34
                index = j;
35
            }
36
        }
37
        int start = (index - maxLen) / 2;
38
        return s.substring(start,start+maxLen);
39
    }
40
}