5. Longest Palindromic Substring 最长回文子串问题

Manacher算法，复杂度O(n)，贴一下自己的代码：
public class Solution {
    public String longestPalindrome(String s) {
        List<Character> s2 = new ArrayList<>();
        int size = s.length();
        int[] p = new int[size * 2 + 2];
        s2.add('$');
        s2.add('#');
        for (int i = 0; i < size; ++i) {
            s2.add(s.charAt(i));
            s2.add('#');
        }
        s2.add('@');
        int index = 0;
        int max = 0;
        int len2 = s2.size();
        for (int i = 1; i < len2 - 1; ++i) {
            if (max > i) {
                p[i] = Math.min(max - i, p[2 * index - i]);
            } else {
                p[i] = 1;
            }
            for (; s2.get(i - p[i]) == s2.get(i + p[i]); p[i] += 1);
            if (p[i] + i > max) {
                max = p[i] + i;
                index = i;
            }
        }
        int res = 0;
        int resIndex = 0;
        for (int i = 1; i < len2 - 1; ++i) {
            if (res < p[i]) {
                res = p[i];
                resIndex = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = resIndex - res + 1; i < resIndex + res; ++i) {
            if (s2.get(i) != '#') {
                sb.append(s2.get(i));
            }
        }
        return sb.toString();
    }
}