Java實(shí)現(xiàn)基于Manacher算法的最長回文子串檢測

以下是使用Java實(shí)現(xiàn)的基于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);
    }
}

代碼的主要思路是將原始字符串進(jìn)行預(yù)處理，在每個(gè)字符之間插入特殊字符#，以避免奇偶長度回文串的問題。然后，使用一個(gè)數(shù)組p來記錄以每個(gè)字符為中心的最長回文子串的半徑長度。通過中心擴(kuò)展法，可以求得每個(gè)位置的最長回文子串半徑長度，并更新最大長度和中心位置。最后，根據(jù)最大長度和中心位置，可以求得最長回文子串的起始位置和長度，進(jìn)而得到最長回文子串。