C语言高效查找并输出最长回文子串391

回文串是指正读和反读都一样的字符串，例如 "level"、"madam"、"racecar" 等。寻找一个字符串中最长的回文子串是一个经典的算法问题，在很多领域都有应用，例如生物信息学中的基因序列分析。本文将详细讲解如何使用 C 语言高效地查找并输出给定字符串中的最长回文子串。

最直接的方法是暴力枚举所有子串，然后判断每个子串是否为回文串。但这是一种效率极低的算法，其时间复杂度为 O(n³)，其中 n 为字符串的长度。对于较长的字符串，这种方法将非常耗时。因此，我们需要寻找更高效的算法。

本文将介绍两种更高效的算法：中心扩展法和Manacher算法。

一、中心扩展法

中心扩展法是一种相对简单的算法，其核心思想是从字符串的每个字符（或字符间隙）出发，向两侧扩展，直到找到回文子串的边界。它可以将时间复杂度降低到 O(n²)。

算法步骤如下：
遍历字符串的每个字符作为中心点。
从中心点向两侧扩展，判断左右字符是否相同。如果相同，则继续扩展。
记录当前找到的最长回文子串的长度和起始位置。
重复步骤 1-3，直到遍历完所有字符。

需要注意的是，回文子串的长度可以是奇数或偶数。对于偶数长度的回文子串，我们需要将中心点设在两个中间字符之间。

以下是用 C 语言实现中心扩展法的代码：```c
#include
#include
void longestPalindrome(char *str) {
int n = strlen(str);
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) {
// 奇数长度回文
int l = i, r = i;
while (l >= 0 && r < n && str[l] == str[r]) {
if (r - l + 1 > maxLen) {
start = l;
maxLen = r - l + 1;
}
l--;
r++;
}
// 偶数长度回文
l = i, r = i + 1;
while (l >= 0 && r < n && str[l] == str[r]) {
if (r - l + 1 > maxLen) {
start = l;
maxLen = r - l + 1;
}
l--;
r++;
}
}
printf("Longest palindrome substring: %.*s", maxLen, str + start);
}
int main() {
char str[] = "babad";
longestPalindrome(str); // Output: bab or aba
char str2[] = "cbbd";
longestPalindrome(str2); // Output: bb
return 0;
}
```

二、Manacher算法

Manacher算法是一种线性时间复杂度的算法，它能够在 O(n) 的时间内找到最长回文子串。该算法巧妙地利用了回文串的对称性，避免了重复计算。

Manacher算法的核心思想是构造一个新的字符串，在原字符串的每个字符之间插入一个特殊字符（例如 '#'），例如 "aba" 变为 "#a#b#a#"。这样，无论回文子串的长度是奇数还是偶数，都可以统一处理为奇数长度的回文子串。

算法会维护一个数组 `p[]`，其中 `p[i]` 表示以 `i` 为中心的最长回文子串的半径。算法利用之前计算的结果来加速后续的计算，从而达到线性时间复杂度。

由于 Manacher 算法较为复杂，这里只给出代码，详细解释请参考相关资料：```c
#include
#include
#include
void manacher(char *s) {
int n = strlen(s);
char *t = (char *)malloc((2 * n + 1) * sizeof(char));
t[0] = '@';
for (int i = 0; i < n; i++) {
t[2 * i + 1] = '#';
t[2 * i + 2] = s[i];
}
t[2 * n + 1] = '$';
n = 2 * n + 1;
int *p = (int *)malloc(n * sizeof(int));
int id = 0, mx = 0;
int maxLen = 0, center = 0;
for (int i = 1; i < n - 1; i++) {
p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
while (t[i + p[i]] == t[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
if (p[i] > maxLen) {
maxLen = p[i];
center = i;
}
}
int start = (center - maxLen) / 2;
printf("Longest palindrome substring: %.*s", maxLen, s + start);
free(t);
free(p);
}
int min(int a, int b) {
return a < b ? a : b;
}

int main() {
char str[] = "babad";
manacher(str); // Output: bab or aba
char str2[] = "cbbd";
manacher(str2); // Output: bb
return 0;
}
```