C语言 实现 最长回文子串 算法 示例代码

<think>好的，我需要回答用户关于C语言实现最长回文子串算法的示例代码的问题。首先，我得确定用户需要的是哪种方法。最长回文子串常见的算法有动态规划、中心扩展法和Manacher算法。根据用户提供的引用，引用[2]提到了动态规划和中心扩展法，引用[3]是Manacher算法，引用[4]可能有中心扩展的代码片段。 用户明确提到需要C语言实现，所以我要参考引用中的C代码部分。引用[3]中的Manacher算法示例可能有用，但用户的问题可能更倾向于动态规划或中心扩展，因为引用[2]和[4]中有相关描述。不过引用[4]的代码看起来是关于统计回文子串数量的，可能不是直接找最长子串。 动态规划在引用[2]中有详细说明，但提供的代码是Java或Python的，需要转换成C语言。中心扩展法可能在引用[4]中部分涉及，但需要调整。而Manacher算法在引用[3]有函数原型，但需要补充完整。 考虑到用户可能需要多种方法的示例，我应选择其中一种或两种来展示。动态规划虽然时间复杂度高，但思路清晰；中心扩展法更高效，适合C语言实现。Manacher算法更高效，但实现稍复杂。 先整理动态规划的C语言实现。根据引用[2]中的描述，动态规划需要一个二维数组dp[i][j]表示i到j是否为回文。初始化长度为1和2的情况，然后逐步扩展。同时记录最长子串的起始位置和长度。 然后，中心扩展法需要遍历每个可能的中心点，向两边扩展。引用[4]中的代码虽然用于统计数量，但可以修改为记录最长回文。Manacher算法在引用[3]中的函数需要实现，可能需要预处理字符串，插入特殊字符，然后计算回文半径。 考虑到用户可能需要完整可运行的代码，我需要确保示例正确且语法无误。动态规划在C中可能遇到内存问题，因为二维数组的大小取决于输入字符串长度，如果字符串很长，可能栈溢出。因此，可能需要动态分配内存，但示例代码需要简洁。 比如，动态规划实现：使用二维数组，初始化单字符和双字符的情况，然后遍历子串长度。记录最长子串的起始和长度，最后提取子串返回。 中心扩展法则需要两个函数，分别处理奇数和偶数长度的回文。或者统一处理，如引用[4]中的循环方式。但用户提供的引用[4]中的代码似乎有错误，比如循环变量和条件可能需要调整。 Manacher算法较为复杂，但更高效，适合处理长字符串。但用户可能更希望看到基础方法的示例，所以优先展示动态规划和中心扩展法。 现在，我需要编写C代码的动态规划版本。例如： 定义函数，输入字符串，输出最长回文子串。使用二维数组dp，初始化所有长度为1的情况，然后长度为2的情况，再处理更长的子串。每次发现更长的回文时更新起始位置和长度。最后用strncpy提取子串。 需要注意C字符串的处理，比如以'\0'结尾，内存分配等。例如，动态分配dp数组，处理字符串长度为0或1的情况。 然后，中心扩展法的实现，遍历每个中心点，向两边扩展，记录最大长度和起始位置。例如，对于每个i，检查i为中心（奇数长度）和i,i+1为中心（偶数长度）的情况。 最后，可能需要考虑释放动态分配的内存，避免内存泄漏。 用户提供的引用[3]中的Manacher函数原型可能不完整，需要补充实现。但Manacher算法需要预处理字符串，例如插入'#'字符，然后计算每个位置的半径数组，找到最大半径对应的位置，再转换为原始字符串的位置。 综合来看，可能先给出动态规划的实现，然后中心扩展法，最后提到Manacher算法并给出示例。不过用户可能只需要其中一种方法的代码。根据引用[2]中的动态规划描述，优先用C实现动态规划方法。 在编写动态规划代码时，需要注意二维数组的创建。例如，使用bool类型（需要包含stdbool.h）或者用int代替。在C中，动态分配二维数组可能使用指针数组，或者一维数组模拟二维。例如： bool **dp = (bool **)malloc(n * sizeof(bool *)); for (int i=0; i<n; i++) dp[i] = (bool *)malloc(n * sizeof(bool)); 然后初始化i==j时为true，j=i+1时比较s[i]和s[j]。接着，长度从3到n，遍历所有可能的起始点i，结束点j=i+len-1，判断s[i]和s[j]是否相等，且dp[i+1][j-1]是否为true。如果满足，则dp[i][j]=true，并记录长度和起始位置。 最后，释放动态分配的数组内存。 但这样的代码可能在处理长字符串时效率较低，但作为示例是可以的。另外，用户可能需要返回找到的子串，因此在C中需要分配足够的内存来存储结果，并在最后添加'\0'。 例如： char* longestPalindrome(char* s) { int n = strlen(s); if (n == 0) return ""; bool **dp = (bool **)malloc(n * sizeof(bool *)); for (int i=0; i<n; i++) { dp[i] = (bool *)malloc(n * sizeof(bool)); memset(dp[i], false, n * sizeof(bool)); dp[i][i] = true; // 单个字符是回文 } int max_len = 1; int start = 0; // 处理长度为2的情况 for (int i=0; i<n-1; i++) { if (s[i] == s[i+1]) { dp[i][i+1] = true; max_len = 2; start = i; } } // 处理长度>=3的情况 for (int len=3; len<=n; len++) { for (int i=0; i <= n-len; i++) { int j = i + len - 1; if (s[i] == s[j] && dp[i+1][j-1]) { dp[i][j] = true; if (len > max_len) { max_len = len; start = i; } } } } // 提取结果 char* res = (char*)malloc((max_len + 1) * sizeof(char)); strncpy(res, s + start, max_len); res[max_len] = '\0'; // 释放内存 for (int i=0; i<n; i++) free(dp[i]); free(dp); return res; } 需要注意的是，该代码需要处理空字符串的情况，以及内存分配是否正确。此外，当所有字符都不相同，最长回文是单个字符。 然后，中心扩展法的实现可能更高效。例如： int expandAroundCenter(char *s, int left, int right) { int n = strlen(s); while (left >=0 && right <n && s[left] == s[right]) { left--; right++; } return right - left -1; } char* longestPalindrome(char* s) { if (strlen(s) <1) return ""; int start =0, end=0; for (int i=0; i<strlen(s); i++) { int len1 = expandAroundCenter(s, i, i); // 奇数长度 int len2 = expandAroundCenter(s, i, i+1); // 偶数长度 int len = len1 > len2 ? len1 : len2; if (len > end - start) { start = i - (len -1)/2; end = i + len/2; } } int length = end - start +1; char* res = (char*)malloc((length +1)*sizeof(char)); strncpy(res, s + start, length); res[length] = '\0'; return res; } 此方法的时间复杂度为O(n^2)，空间复杂度为O(1)，更高效，适合C语言实现。可能用户更希望看到这种实现，因为引用[2]中提到了中心扩展法。 根据引用[4]中的代码，虽然存在错误，但可以调整为中心扩展的实现。例如，统计最长子串而非数量，所以需要比较长度并记录最大时的位置。 最后，Manacher算法的时间复杂度为O(n)，但实现复杂。引用[3]中的函数原型可能需要补充。例如，预处理字符串，计算每个中心的回文半径，然后找到最大的那个。 例如，预处理字符串插入'#'，例如将"abc"变成"#a#b#c#"，然后维护一个数组P记录每个中心的半径。同时维护C和R表示当前最右回文的中心和右边界。遍历每个字符，利用对称性减少计算。 具体实现可能较为复杂，需要处理奇偶长度的问题。例如： void Manacher(char *str, char *maxpalindrome) { // 预处理字符串 int len = strlen(str); char *T = (char*)malloc(2*len +3); T[0] = '$'; T[1] = '#'; for (int i=0; i<len; i++) { T[2*i +2] = str[i]; T[2*i +3] = '#'; } T[2*len +2] = '\0'; int n = 2*len +2; int *P = (int*)malloc(n * sizeof(int)); int C=0, R=0; int max_len=0, center=0; for (int i=1; i<n; i++) { int mirror = 2*C -i; if (i < R) { P[i] = (R -i) < P[mirror] ? (R -i) : P[mirror]; } else { P[i] =0; } // 扩展 while (T[i + P[i] +1] == T[i - P[i] -1]) { P[i]++; } if (i + P[i] > R) { C =i; R =i + P[i]; } if (P[i] > max_len) { max_len = P[i]; center =i; } } // 计算原始字符串中的位置 int start = (center - max_len)/2; strncpy(maxpalindrome, str + start, max_len); maxpalindrome[max_len] = '\0'; free(T); free(P); } 但用户需要示例代码，所以需要整合到函数中，并正确处理输入输出。 综上所述，用户可能需要动态规划或中心扩展法的C代码。考虑到效率和实现复杂度，中心扩展法可能更合适。因此，在回答中提供中心扩展法的示例代码，并简要说明动态规划和Manacher算法，同时引用相关文献。 最后，生成相关问题，比如不同算法的时间复杂度、优化方法等。</think>### C语言实现最长回文子串算法示例 #### 方法一：动态规划法 动态规划通过二维数组记录子串是否为回文，逐步扩展子串长度。以下是C语言实现代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> char* longestPalindrome(char* s) { int n = strlen(s); if (n == 0) return ""; // 动态分配二维数组 bool **dp = (bool **)malloc(n * sizeof(bool *)); for (int i = 0; i < n; i++) { dp[i] = (bool *)malloc(n * sizeof(bool)); memset(dp[i], false, n * sizeof(bool)); dp[i][i] = true; // 单个字符是回文 } int max_len = 1, start = 0; // 处理长度为2的子串 for (int i = 0; i < n - 1; i++) { if (s[i] == s[i + 1]) { dp[i][i + 1] = true; max_len = 2; start = i; } } // 处理长度≥3的子串 for (int len = 3; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s[i] == s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; if (len > max_len) { max_len = len; start = i; } } } } // 提取结果并释放内存 char* res = (char *)malloc((max_len + 1) * sizeof(char)); strncpy(res, s + start, max_len); res[max_len] = '\0'; for (int i = 0; i < n; i++) free(dp[i]); free(dp); return res; } // 测试代码 int main() { char s[] = "babad"; char* result = longestPalindrome(s); printf("最长回文子串: %s\n", result); // 输出 "bab" 或 "aba" free(result); return 0; } ``` **说明**： - 时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$，适用于较短字符串[^2]。 - 通过二维数组`dp[i][j]`记录子串`s[i...j]`是否为回文，逐步扩展长度。 --- #### 方法二：中心扩展法 中心扩展法通过遍历每个可能的中心点向两侧扩展，更高效： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> int expandAroundCenter(char* s, int left, int right) { int n = strlen(s); while (left >= 0 && right < n && s[left] == s[right]) { left--; right++; } return right - left - 1; // 返回回文长度 } char* longestPalindrome(char* s) { if (strlen(s) == 0) return ""; int start = 0, end = 0; for (int i = 0; i < strlen(s); i++) { int len1 = expandAroundCenter(s, i, i); // 奇数长度 int len2 = expandAroundCenter(s, i, i+1); // 偶数长度 int len = len1 > len2 ? len1 : len2; if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } int length = end - start + 1; char* res = (char *)malloc((length + 1) * sizeof(char)); strncpy(res, s + start, length); res[length] = '\0'; return res; } // 测试代码 int main() { char s[] = "cbbd"; char* result = longestPalindrome(s); printf("最长回文子串: %s\n", result); // 输出 "bb" free(result); return 0; } ``` **说明**： - 时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，适用于中等长度字符串。 - 遍历每个字符作为中心，分别处理奇偶长度的回文。 --- #### 方法三：Manacher算法 Manacher算法通过预处理字符串将时间复杂度优化到$O(n)$： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> void Manacher(char* str, char* maxpalindrome) { // 预处理字符串（插入特殊字符） int len = strlen(str); char* T = (char*)malloc(2 * len + 3); T[0] = '$'; // 起始符 T[1] = '#'; for (int i = 0; i < len; i++) { T[2 * i + 2] = str[i]; T[2 * i + 3] = '#'; } T[2 * len + 2] = '\0'; int n = 2 * len + 2; int* P = (int*)malloc(n * sizeof(int)); // 记录各中心的最长回文半径 memset(P, 0, n * sizeof(int)); int C = 0, R = 0; // 当前最右回文的中心和右边界 int max_radius = 0, max_center = 0; for (int i = 1; i < n; i++) { int mirror = 2 * C - i; // 对称点 if (i < R) P[i] = (R - i < P[mirror]) ? R - i : P[mirror]; // 中心扩展 while (T[i + P[i] + 1] == T[i - P[i] - 1]) P[i]++; // 更新最右边界 if (i + P[i] > R) { C = i; R = i + P[i]; } // 记录最大值 if (P[i] > max_radius) { max_radius = P[i]; max_center = i; } } // 转换为原始字符串的位置 int start = (max_center - max_radius) / 2; strncpy(maxpalindrome, str + start, max_radius); maxpalindrome[max_radius] = '\0'; free(T); free(P); } // 测试代码 int main() { char s[] = "abacdfgdcaba"; char result[100]; Manacher(s, result); printf("最长回文子串: %s\n", result); // 输出 "aba" return 0; } ``` **说明**： - 时间复杂度：$O(n)$，空间复杂度：$O(n)$，适用于超长字符串[^3]。 - 通过插入特殊字符统一处理奇偶长度回文，利用对称性减少重复计算。 --- ###