使用c语言解决输入一串字符串，求其最长的回文子串的长度 输入提示: "Please input string:\n" 输入格式: "%s" 输出格式: "%5d" 程序运行结果实例1： Please input string: ↙ babad 3 程序运行结果实例2： Please input string: ↙ cbbd 2

下面是使用动态规划的 C 语言代码实现，同样可以求出给定字符串的最长回文子串长度：

#include <stdio.h>
#include <string.h>

#define MAXN 1005

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char s[MAXN];
    printf("Please input string:\n");
    scanf("%s", s);

    int n = strlen(s);
    int dp[MAXN][MAXN] = {0};

    // 初始化长度为 1 和 2 的回文子串
    int max_len = 1;
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
            max_len = 2;
        }
    }

    // 枚举回文子串长度 k，从 3 开始
    for (int k = 3; k <= n; k++) {
        // 枚举左端点 i
        for (int i = 0; i <= n - k; i++) {
            // 计算右端点 j
            int j = i + k - 1;
            // 判断 s[i:j+1] 是否为回文子串
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = 1;
                max_len = k;
            }
        }
    }

    printf("%5d\n", max_len);
    return 0;
}

需要注意的是，这个算法的时间复杂度为 $O(n^2)$，其中 $n$ 是字符串的长度，空间复杂度也为 $O(n^2)$，可以通过进一步优化来降低空间复杂度。