Java中如何檢測并提取字符串中的最長回文路徑

在Java中，要檢測并提取字符串中的最長回文路徑，可以使用動態規劃方法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LongestPalindromicPath {
    public static void main(String[] args) {
        String input = "abacdfgdcabba";
        List<Integer> result = findLongestPalindromicPath(input, 2);
        System.out.println("最長回文路徑長度: " + result.get(0));
        System.out.println("最長回文路徑: " + result.get(1));
    }

    public static List<Integer> findLongestPalindromicPath(String s, int k) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 0;
        int[] longestPalindromeEnd = new int[n];

        // 初始化長度為1和2的回文子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                maxLength = 2;
                longestPalindromeEnd[i] = i;
                longestPalindromeEnd[i + 1] = i;
            }
        }

        // 使用動態規劃構建更長的回文子串
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    maxLength = len;
                    longestPalindromeEnd[i] = j;
                }
            }
        }

        // 從最長回文子串的中心向兩邊擴展，提取路徑
        List<Integer> path = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (dp[i][i]) {
                path.add(0);
            }
            if (dp[i][longestPalindromeEnd[i]]) {
                path.add(longestPalindromeEnd[i] - i + 1);
            }
        }

        // 反轉路徑，使其從起點到終點
        Collections.reverse(path);

        // 移除首尾字符，使其符合題目要求的路徑長度
        if (path.size() > k) {
            path.remove(0);
            path.remove(path.size() - 1);
        }

        return path;
    }
}

這個程序首先使用動態規劃方法找到字符串中的最長回文子串，然后從回文子串的中心向兩邊擴展，提取路徑。最后，根據題目要求的長度k，移除首尾字符。