请告诉我C语言代码
时间: 2024-02-25 07:58:32 浏览: 24
好的,下面是 C 语言的代码实现:
```c
#include <stdio.h>
#include <string.h>
int dp[1005][1005]; // 状态数组
char s[1005]; // 输入字符串
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s);
int n = strlen(s);
memset(dp, 0, sizeof(dp));
int max_len = 1, start = 0, end = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = 1; // 初始化
if (i < n - 1 && s[i] == s[i+1]) {
dp[i][i+1] = 1; // 初始化
max_len = 2;
start = i;
end = i + 1;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = 1;
if (len > max_len) {
max_len = len;
start = i;
end = j;
}
}
}
}
printf("%.*s\n", end - start + 1, s + start); // 输出最长回文子串
}
return 0;
}
```
这段代码中,我们使用了 dp 数组来记录状态,使用 memset 函数来初始化 dp 数组,使用 strlen 函数来获取字符串的长度,使用 scanf 函数来读入测试数据。
在主函数中,我们先读入测试数据的组数 T,然后进行 T 次操作。每次操作中,我们先读入字符串 s,然后在 dp 数组中初始化长度为 1 或 2 的子串,接着对于长度大于等于 3 的子串进行状态转移,最后输出最长回文子串。
注意,我们使用了 %.*s 格式化输出最长回文子串,它表示输出 s + start 到 s + end 的字符串。这种输出方式可以避免使用额外的字符串数组,提高代码的效率。
总之,这是一个简单而有效的动态规划解法,可以用来解决最长回文子串问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)