C语言写最长回文子串
时间: 2024-10-23 18:15:33 浏览: 103
在C语言中,寻找一个字符串中最长的回文子串可以使用动态规划算法来解决。下面是一个简单的示例,使用了Manacher's Algorithm,它是一种改进过的策略,可以在O(n)的时间复杂度内找到最长回文子串:
```c
#include <stdio.h>
#include <string.h>
int longestPalindrome(char* s) {
if (s == NULL || strlen(s) == 0) return 0;
int n = strlen(s);
char t[n + 2]; // 创建新的字符串,添加特殊字符 '#' 和 '\0'
for (int i = 0; i < n; ++i) {
t[i+1] = s[i];
t[i+1] = (t[i+1] >= 'a' && t[i+1] <= 'z') ? t[i+1] - 'a' + 'A' : t[i+1]; // 将所有字母转大写
}
t[0] = '#';
t[n+1] = '#';
int p[n+2], maxLen = 1, center = 0, right = 0;
p[0] = p[1] = 0;
for (int i = 2; i <= n+1; ++i) {
int mirror = 2 * center - i;
if (right > i) {
p[i] = min(right - i, p[mirror]);
}
while (t[i+p[i]+1] == t[i-p[i]-1]) { // 检查边界是否回文
p[i]++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
}
}
int start = (center - maxLen) / 2;
return s[start:start+maxLen];
}
int main() {
char str[] = "babad";
printf("Longest palindrome substring is: %s\n", longestPalindrome(str));
return 0;
}
```
阅读全文
相关推荐
















