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，移除首尾字符。