高效求解最长回文子串（C语言Manacher算法详解）

Manacher算法核心思想

Manacher算法的关键在于以下两点：

1. 预处理字符串：在原字符串的每个字符之间插入特殊符号（如 #），将奇偶长度回文统一处理。
2. 利用回文对称性：维护一个“最右回文边界”R 和其对应的中心 C，利用已计算的信息避免重复比较。

步骤详解

1. 预处理字符串

例如原字符串 s = "abba"，预处理后变为 t = "#a#b#b#a#"。这样所有回文都变成奇数长度，便于统一处理。

2. 定义数组 P

P[i] 表示以位置 i 为中心的回文半径（包含中心）。例如在 t = "#a#b#b#a#" 中，若 P[4] = 4，说明以索引4为中心的回文长度为4，对应原字符串中的 "bb"。

3. 利用对称性加速计算

设当前遍历到位置 i，已知最右边界 R 和中心 C：

• 若 i < R，则可利用对称点 j = 2*C - i 的信息，令 P[i] = min(P[j], R - i)。
• 然后尝试向两边扩展，更新 P[i]。
• 若扩展后超过 R，则更新 C = i，R = i + P[i]。

C语言完整实现

#include <stdio.h>#include <stdlib.h>#include <string.h>// 预处理字符串：在字符间插入 '#'char* preprocess(const char* s) {    int len = strlen(s);    char* t = (char*)malloc(sizeof(char) * (2 * len + 3));    t[0] = '^'; // 起始哨兵    t[1] = '#';    for (int i = 0; i < len; i++) {        t[2 * i + 2] = s[i];        t[2 * i + 3] = '#';    }    t[2 * len + 2] = '$'; // 结束哨兵    t[2 * len + 3] = '\0';    return t;}int manacher(const char* s) {    char* t = preprocess(s);    int n = strlen(t);    int* P = (int*)calloc(n, sizeof(int));        int C = 0, R = 0; // 中心和最右边界    int maxLen = 0;    for (int i = 1; i < n - 1; i++) {        int mirror = 2 * C - i; // i 关于 C 的对称点                // 如果 i 在 R 内部，利用对称性        if (i < R) {            P[i] = (R - i) < P[mirror] ? (R - i) : P[mirror];        }                // 尝试扩展回文        while (t[i + (1 + P[i])] == t[i - (1 + P[i])]) {            P[i]++;        }                // 如果扩展超过了 R，更新中心和边界        if (i + P[i] > R) {            C = i;            R = i + P[i];        }                // 更新最大回文长度        if (P[i] > maxLen) {            maxLen = P[i];        }    }        free(t);    free(P);    return maxLen;}int main() {    char s[] = "abcbabba";    int len = manacher(s);    printf("最长回文子串长度: %d\n", len);    return 0;}

代码说明

• 使用 ^ 和 $ 作为哨兵，防止越界。
• P[i] 存储的是预处理后字符串中以 i 为中心的回文半径。
• 最终返回的 maxLen 即为原字符串中最长回文子串的长度。

总结

通过本教程，你已经掌握了 Manacher算法 的核心思想与 C语言实现。该算法是解决最长回文子串问题的高效方案，也是面试和竞赛中的高频考点。建议动手敲一遍代码，加深理解！

记住这四个关键词：Manacher算法、C语言回文字符串、最长回文子串、字符串算法教程，它们将帮助你在搜索引擎中快速找到相关资源。