数据结构与算法面试题：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。（提示：使用动态规划或者中心扩散）

#include <iostream>
#include <string>

using namespace std;

// 中心扩散法寻找回文子串
string longestPalindrome(string s) {
    int n = s.size();
    if (n < 2) return s; // 字符串长度小于2则直接返回s

    int start = 0, len = 0; // 记录最长回文子串的起点和长度
    for (int i = 0; i < n; ++i) { // 枚举中心点i
        // 分别处理回文子串长度为奇数、偶数的情况
        for (int k = 0; k < 2; ++k) {
            int left = i, right = i + k;
            while (left >= 0 && right < n && s[left] == s[right]) {
                --left;
                ++right;
            }
            // 当前回文子串长度为(right - 1) - (left + 1) + 1 = right - left - 1
            int cur_len = right - left - 1;
            if (cur_len > len) { // 更新最长回文子串
                start = left + 1;
                len = cur_len;
            }
        }
    }
    return s.substr(start, len); // 返回最长回文子串
}

int main() {
    string s = "babad";
    string ans = longestPalindrome(s);
    cout << ans << endl;
    return 0;
}

public class Main {

    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        int start = 0, len = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < 2; ++k) {
                int left = i, right = i + k;
                while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                    --left;
                    ++right;
                }
                int curLen = right - left - 1;
                if (curLen > len) {
                    start = left + 1;
                    len = curLen;
                }
            }
        }
        return s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "babad";
        String ans = longestPalindrome(s);
        System.out.println(ans); // "bab"
    }
}