题目描述 已知字符串str。 输出字符串str中最长回文串的长度。 输入描述: 输入字符串s.(1<=len(str)<=10000) 输出描述: 输出答案用c编写,直接给出最省时的示例代码
时间: 2023-02-06 22:14:41 浏览: 44
以下是在 C 语言中求出字符串 str 中最长回文串的长度的示例代码:
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
char str[10001];
scanf("%s", str);
int len = strlen(str);
int dp[len][len];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
for (int i = len - 1; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
if (str[i] == str[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", dp[0][len - 1]);
return 0;
}
该代码使用动态规划的方法求解。它定义了一个二维数组 dp,其中 dp[i][j] 表示从字符串 str 的第 i 个字符开始到第 j 个字符结束的子串中最长回文子串的长度。它从后往前遍历字符串 str,每次枚举两个位置 i 和 j,如果 str[i] == str[j],则 dp[i][j] = dp[i + 1][j - 1] + 2,否则 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。最后,输出 dp[0][len - 1] 即可得到字符串 str 中最长回文子串的长度。