第23章字符串中查找最长回文子串

课程目录第23章字符串中查找最长回文子串

第23章：字符串中查找最长回文子串——中心扩展法

回文串，说白了就是正着读反着读都一样。比如"aba"、"level"、"上海自来水来自海上"。找最长回文子串，是字符串处理里的经典问题。我当年刚入行时，面试就被问过这道题。那时候我写了个O(n³)的暴力解法，面试官笑了笑说"回去等通知吧"——嗯，再也没有通知了。

今天咱们聊的中心扩展法，时间复杂度O(n²)，空间复杂度O(1)。虽然不是最优解（Manacher算法才是O(n)），但胜在思路直观、代码好写、不容易出错。我在实际项目中，90%的场景都用它，因为n通常不超过几千，O(n²)完全够用。

23.1 什么是回文子串？

先明确定义：

子串：原字符串中连续的一段字符
回文：正反读相同
最长回文子串：所有回文子串中，长度最大的那个

举个例子：

字符串: "babad"
回文子串: "bab" 和 "aba" 都是长度3
最长回文子串: "bab" 或 "aba"（返回任意一个即可）

你想想看，如果字符串长度是1000，暴力枚举所有子串再判断是否回文，复杂度是O(n³)——这谁受得了？

23.2 中心扩展法的核心思想

中心扩展法的思路很简单：每个回文串都有一个"中心"，从这个中心向两边扩展，就能得到完整的回文串。

但要注意：回文串有两种类型：

奇数长度：中心是一个字符，比如"aba"的中心是'b'
偶数长度：中心是两个字符之间，比如"abba"的中心在"bb"之间

所以，我们需要对每个位置，分别尝试两种扩展：

以当前字符为中心，向两边扩展（奇数回文）
以当前字符和下一个字符的间隙为中心，向两边扩展（偶数回文）

我个人习惯把这两种情况分开处理，代码更清晰。有些同学喜欢合并成一个函数，但我觉得那样反而容易搞混。

23.3 代码实现

先看完整代码，我再逐行解释：

#include <stdio.h>
#include <string.h>

// 从中心向两边扩展，返回找到的回文子串长度
int expandAroundCenter(char* s, int left, int right) {
    int len = strlen(s);
    while (left >= 0 && right < len && s[left] == s[right]) {
        left--;
        right++;
    }
    // 注意：退出循环时，left和right已经多走了一步
    // 回文子串的范围是 [left+1, right-1]
    // 长度 = (right-1) - (left+1) + 1 = right - left - 1
    return right - left - 1;
}

char* longestPalindrome(char* s) {
    int len = strlen(s);
    if (len < 2) return s;  // 单个字符或空串，本身就是回文
    
    int start = 0;   // 最长回文子串的起始位置
    int maxLen = 1;  // 最长回文子串的长度（至少为1）
    
    for (int i = 0; i < len; i++) {
        // 情况1：奇数长度回文，中心在 i
        int len1 = expandAroundCenter(s, i, i);
        // 情况2：偶数长度回文，中心在 i 和 i+1 之间
        int len2 = expandAroundCenter(s, i, i + 1);
        
        int curLen = len1 > len2 ? len1 : len2;
        if (curLen > maxLen) {
            maxLen = curLen;
            // 计算起始位置：中心位置 - (回文长度-1)/2
            start = i - (curLen - 1) / 2;
        }
    }
    
    // 提取子串（这里直接修改原字符串，实际使用时建议复制）
    char* result = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(result, s + start, maxLen);
    result[maxLen] = '\0';
    return result;
}

23.4 关键细节解析

1. expandAroundCenter函数的返回值

这个函数返回的是回文子串的长度。为什么是 right - left - 1？

你看，当while循环退出时，left和right已经指向了不满足条件的字符。比如字符串"aba"，从i=1（字符'b'）开始扩展：

初始：left=1, right=1
第1步：s[1]==s[1] → left=0, right=2
第2步：s[0]==s[2] → left=-1, right=3
退出循环：left=-1, right=3

回文子串的范围是[left+1, right-1] = [0, 2]，长度 = 2 - 0 + 1 = 3。而right - left - 1 = 3 - (-1) - 1 = 3。完美！

2. 起始位置的计算

找到更长的回文后，需要计算它在原字符串中的起始位置：

start = i - (curLen - 1) / 2;

这个公式对奇偶都适用。举个例子：

奇数回文"aba"，中心i=1，长度3 → start = 1 - (3-1)/2 = 1 - 1 = 0 ✓
偶数回文"abba"，中心i=1（左中心），长度4 → start = 1 - (4-1)/2 = 1 - 1 = 0 ✓

重点记忆：中心扩展法的核心就是两个循环——外层遍历每个中心，内层向两边扩展。时间复杂度O(n²)，空间复杂度O(1)。

23.5 我踩过的坑

坑1：忘记处理偶数回文

我曾经在项目里写过一个版本，只考虑了奇数回文。结果测试"abba"时，返回的是"bb"而不是"abba"。排查了半天才发现，原来偶数回文的中心在两个字符之间。从那以后，我每次写中心扩展法，都会在注释里写上"别忘了偶数情况"。

坑2：边界条件搞错

while循环里，一定要先判断left和right是否越界，再比较字符。如果写成 while (s[left] == s[right] && left >= 0 && right < len)，当left=-1时，访问s[-1]直接就崩了。C语言不检查数组越界，这种bug特别隐蔽。

坑3：起始位置算错

我刚开始学的时候，start的计算公式写错过好几次。后来我总结了一个口诀："中心减半长减一"——start = i - (curLen - 1) / 2。记住这个，再也没错过。

23.6 中心扩展法的可视化

为了让你更直观地理解，我画了一张图：

23.7 复杂度分析

指标	值	说明
时间复杂度	O(n²)	外层循环n次，内层扩展最多n次
空间复杂度	O(1)	只用了几个变量，不随输入规模变化
适用场景	字符串长度 ≤ 5000	超过5000建议用Manacher算法

小技巧：如果你不确定字符串长度，可以在函数开头加个判断：如果len > 5000，就改用Manacher算法。我一般在工具函数里这么写，兼顾效率和通用性。

23.8 优化思路

中心扩展法还能优化吗？当然可以。我分享两个实用技巧：

技巧1：提前终止

如果当前中心位置i，即使扩展到字符串两端，最大可能长度也只有 2 * min(i, len-1-i) + 1。如果这个值已经小于当前maxLen，就可以直接跳过这个中心。

for (int i = 0; i < len; i++) {
    // 最大可能长度
    int maxPossible = 2 * (i < len-1-i ? i : len-1-i) + 1;
    if (maxPossible <= maxLen) continue;  // 不可能更长了
    
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, i + 1);
    // ... 后续处理
}

技巧2：从中间开始

如果回文串大概率在字符串中间区域，可以从中间位置开始遍历，这样能更快找到较长的回文，从而利用技巧1跳过更多中心。

注意：技巧2只适用于特定场景，比如你知道输入数据有某种规律。通用场景下，还是老老实实从左到右遍历吧。我曾经在通用库中用了"从中间开始"的优化，结果被同事吐槽"你这代码有玄学成分"——哈哈，确实有点。

23.9 实战经验总结

我在一个日志分析项目中，需要从大量日志中提取最长的重复模式。日志行长度通常不超过2000字符，用中心扩展法完全够用。当时我写了两个版本：

版本A：暴力法O(n³)，处理1000行日志需要3秒
版本B：中心扩展法O(n²)，处理同样数据只需要0.05秒

你看，一个算法优化，性能提升了60倍。这就是算法的力量。

最后，送你一句话：中心扩展法虽然简单，但它是理解更高级算法（如Manacher）的基础。把今天的内容吃透，以后学Manacher算法会轻松很多。

好了，这一章就到这里。代码多写几遍，坑多踩几次，自然就记住了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录