用C语言写一个字符串s,找到s中最长的回文子串
时间: 2024-02-26 20:57:51 浏览: 61
寻找字符串的最长回文序列, C语言实现
5星 · 资源好评率100%
好的,下面是一个简单的 C 代码实现,采用中心扩展法:
```c
#include <stdio.h>
#include <string.h>
char* longestPalindrome(char* s) {
if (s == NULL || strlen(s) == 0) {
return "";
}
int len = strlen(s);
int start = 0, end = 0;
for (int i = 0; i < len; i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int maxLen = len1 > len2 ? len1 : len2;
if (maxLen > end - start + 1) {
start = i - (maxLen - 1) / 2;
end = i + maxLen / 2;
}
}
char* ans = (char*) malloc(sizeof(char) * (end - start + 2));
strncpy(ans, s + start, end - start + 1);
ans[end - start + 1] = '\0';
return ans;
}
int expandAroundCenter(char* s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < strlen(s) && s[L] == s[R]) {
L--;
R++;
}
return R - L - 1;
}
int main() {
char s[] = "babad";
char* ans = longestPalindrome(s);
printf("%s\n", ans);
free(ans);
return 0;
}
```
代码中的 `longestPalindrome` 函数用于找到最长回文子串,其中 `expandAroundCenter` 函数用于中心扩展。在 `longestPalindrome` 函数中,我们枚举了所有可能的回文中心,分别计算以它们为中心的回文串长度,最终得到最长的回文子串。代码中使用了 `malloc` 函数动态分配内存,需要在使用完后使用 `free` 函数释放内存。
阅读全文