马拉车算法 java

public class Solution1 {
    public static void main(String[] args) {
        System.out.println(new Solution1().longestPalindrome("abcdcba"));

        System.out.println(new Solution1().longestPalindrome("abc"));

        System.out.println(new Solution1().longestPalindrome("aabc"));

        System.out.println(new Solution1().longestPalindrome("aabccc"));

        System.out.println(new Solution1().longestPalindrome("abcecdef"));

        System.out.println(new Solution1().longestPalindrome("aaaaaaaaaaba"));
    }

    public String longestPalindrome(String s) {
        StringBuilder builder = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            builder.append(s.charAt(i));
            builder.append("#");
        }
        String str = builder.toString();
        List<Integer> list = new ArrayList<>();
        int center = -1;
        int right = -1;
        int leftIndex = -1;
        int rightIndex = -1;
        for (int i = 0; i < str.length(); i++) {
            int cut;
            if (i <= right) {
                int curLeft = center * 2 - i;
                cut = Math.min(list.get(curLeft), i - center);
                cut = expand(str, i - cut - 1, i + cut + 1);
            } else {
                cut = expand(str, i - 1, i + 1);
            }
            list.add(cut);
            if (i + cut > right) {
                right = i + cut;
                center = i;
            }
            if (cut * 2 + 1 > rightIndex - leftIndex) {
                rightIndex = i + cut;
                leftIndex = i - cut;
            }
        }
        StringBuilder result = new StringBuilder();
        for (int i = leftIndex; i <= rightIndex; i++) {
            if (str.charAt(i) != '#') {
                result.append(str.charAt(i));
            }
        }
        return result.toString();
    }

    private int expand(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return (right - left - 2) / 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63