Java实现基于Manacher算法的最长回文子串检测

以下是使用Java实现的基于Manacher算法的最长回文子串检测的示例代码：

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        String s = "babad";
        System.out.println("The longest palindromic substring is: " + longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        String t = sb.toString();
        int[] p = new int[t.length()];
        int maxLen = 0;
        int center = 0;
        int maxRight = 0;
        for (int i = 0; i < t.length(); i++) {
            if (i < maxRight) {
                int j = center - (i - center);
                p[i] = Math.min(maxRight - i, p[j]);
            }
            int left = i - (1 + p[i]);
            int right = i + (1 + p[i]);
            while (left >= 0 && right < t.length() && t.charAt(left) == t.charAt(right)) {
                p[i]++;
                left--;
                right++;
            }
            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                center = i;
            }
            if (p[i] > maxLen) {
                maxLen = p[i];
            }
        }
        int start = (center - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}

代码的主要思路是将原始字符串进行预处理，在每个字符之间插入特殊字符#，以避免奇偶长度回文串的问题。然后，使用一个数组p来记录以每个字符为中心的最长回文子串的半径长度。通过中心扩展法，可以求得每个位置的最长回文子串半径长度，并更新最大长度和中心位置。最后，根据最大长度和中心位置，可以求得最长回文子串的起始位置和长度，进而得到最长回文子串。