TikTok 最长回文子串：中心扩展到 Manacher 的线性证明

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 连续子串，按Unicode code point比较；空字符串返回空，同长度取最早开始位置。
• 不做大小写折叠、标点删除或Unicode归一化；用户感知字符如组合音标需另定义。
• 使用odd/even两个半径数组，不假设某个特殊字符绝不会出现在输入中。

解题路线

1. 中心扩展对n个字符中心及n−1个缝隙逐次比较，简单且O(n²)最坏；全相同字符会反复扩到很远。Manacher复用先前回文中已知的对称区间，避免重复确认内部字符。
2. odd[i]是以i为中心、包含中心的半径，区间[i−r+1,i+r−1]；even[i]以i−1与i之间为中心，半径r覆盖[i−r,i+r−1]。两者下标定义不同，镜像公式也不同。
3. 维护当前已知最靠右的回文[left,right]。新中心i在right内时，镜像半径至少能保证到min(镜像半径,right−i+1)；odd镜像left+right−i，even镜像left+right−i+1。
4. 镜像超出当前边界的部分未知，不能照抄整个镜像半径；从保证长度开始真实向两端比较。如果得到更远右端点，才更新left/right。
5. 线性时间来自right单调增加：外部未知区域的成功扩展会推进最右边界，总共O(n)次；边界内复制不再逐字符重算，每个中心最多一次停止比较。奇偶各一次扫描仍是O(n)。
6. 答案用start/length比较，长度更大或同长start更小才替换。最后一次切片输出，避免每次刷新答案都复制长子串而改变线性结论。
7. 回文子串不是回文子序列；后者允许跳过字符，Manacher不适用。若要求统计所有回文出现次数，可按半径求和；输出全部子串本身可能二次多。

手动走一遍

babad有bab和aba同长，本文取起点更早的bab。cbbd的答案bb必须由偶数中心找到。输入含#时也正常，因为未插入字符分隔符；界🙂界按code point是三字符回文。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Unicode code-point palindrome. Earliest start breaks longest-length ties.
Separate odd/even radius arrays avoid sentinel collisions.
"""


def longest_palindrome(text):
    n = len(text)
    best_start = best_length = 0
    odd = [0] * n
    left, right = 0, -1
    for i in range(n):
        radius = 1 if i > right else min(odd[left + right - i], right - i + 1)
        while i - radius >= 0 and i + radius < n and text[i - radius] == text[i + radius]:
            radius += 1
        odd[i] = radius
        start, length = i - radius + 1, 2 * radius - 1
        if length > best_length or (length == best_length and start < best_start):
            best_start, best_length = start, length
        if i + radius - 1 > right:
            left, right = start, i + radius - 1
    even = [0] * n
    left, right = 0, -1
    for i in range(n):
        radius = 0 if i > right else min(even[left + right - i + 1], right - i + 1)
        while i - radius - 1 >= 0 and i + radius < n and text[i - radius - 1] == text[i + radius]:
            radius += 1
        even[i] = radius
        start, length = i - radius, 2 * radius
        if length > best_length or (length == best_length and start < best_start):
            best_start, best_length = start, length
        if i + radius - 1 > right:
            left, right = start, i + radius - 1
    return text[best_start:best_start + best_length]

复杂度

时间O(n)，odd/even与输出O(n)空间，工作变量O(1)。输入以grapheme cluster定义时需要先分词，该预处理和输出映射应另计。

易错点与追问

容易失分的边界

• 偶数中心镜像沿用odd公式。
• 镜像半径越过right仍不做比较。
• 频繁切片让输出复制变二次。
• 把子串当子序列。

继续深挖

• 怎样数出全部回文出现次数？
• 如何在线支持追加字符？
• 若只要O(1)工作空间接受什么时间界？
• 如何返回所有同长最优答案？