babad

bab

cbbd

bb

import sys

def longest_palindrome_dp(s):
    """ 使用动态规划找到最长回文子串 """
    n = len(s)
    if n == 0:
        return ""

    # 初始化 DP 数组，dp[i][j] 表示 s[i:j+1] 是否是回文
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1  # 记录最长回文子串的起始索引和长度

    # 所有单个字符都是回文
    for i in range(n):
        dp[i][i] = True

    # 处理长度大于 1 的子串
    for length in range(2, n + 1):  # 从长度 2 开始遍历
        for i in range(n - length + 1):  # 遍历起始索引
            j = i + length - 1  # 计算子串的结束索引
            if s[i] == s[j]:  # 首尾字符相等
                if length == 2 or dp[i + 1][j - 1]:  # 两个字符或内部是回文
                    dp[i][j] = True
                    if length > max_length:  # 更新最长回文
                        start = i
                        max_length = length

    return s[start:start + max_length]  # 返回最长回文子串

def main():
    """ 读取输入并调用求解函数 """
    s = sys.stdin.readline().strip()  # 读取输入字符串
    print(longest_palindrome_dp(s))  # 输出最长回文子串

if __name__ == "__main__":
    main()

import java.util.*;

public class Main {
    public static String longestPalindromeDP(String s) {
        int n = s.length();
        if (n == 0) return "";

        // 初始化 DP 数组
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1; // 记录最长回文子串的起始索引和长度

        // 所有单个字符都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 处理长度大于 1 的子串
        for (int length = 2; length <= n; length++) {  // 子串长度从 2 开始
            for (int i = 0; i <= n - length; i++) {  // 遍历起始索引
                int j = i + length - 1;  // 计算子串的结束索引
                if (s.charAt(i) == s.charAt(j)) {  // 首尾字符相等
                    if (length == 2 || dp[i + 1][j - 1]) {  // 两个字符或内部是回文
                        dp[i][j] = true;
                        if (length > maxLength) {  // 更新最长回文
                            start = i;
                            maxLength = length;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);  // 返回最长回文子串
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();  // 读取输入字符串
        System.out.println(longestPalindromeDP(s));  // 输出最长回文子串
        sc.close();
    }
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestPalindromeDP(string s) {
    int n = s.size();
    if (n == 0) return "";

    // 初始化 DP 数组
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLength = 1;  // 记录最长回文子串的起始索引和长度

    // 所有单个字符都是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // 处理长度大于 1 的子串
    for (int length = 2; length <= n; length++) {  // 子串长度从 2 开始
        for (int i = 0; i <= n - length; i++) {  // 遍历起始索引
            int j = i + length - 1;  // 计算子串的结束索引
            if (s[i] == s[j]) {  // 首尾字符相等
                if (length == 2 || dp[i + 1][j - 1]) {  // 两个字符或内部是回文
                    dp[i][j] = true;
                    if (length > maxLength) {  // 更新最长回文
                        start = i;
                        maxLength = length;
                    }
                }
            }
        }
    }
    return s.substr(start, maxLength);  // 返回最长回文子串
}

int main() {
    string s;
    cin >> s;  // 读取输入字符串
    cout << longestPalindromeDP(s) << endl;  // 输出最长回文子串
    return 0;
}