BISHI94　【模板】马拉车算法¶

中等通过率 47.9%python3样例通过牛客 AC

讲解章节：回文

一句话

求最长回文子串的长度，|S| <= 1e6。

解题思路¶

这题考什么¶

Manacher（马拉车算法，线性求出每个中心的回文半径，见回文）。朴素做法「枚举中心向两边扩」是 O(n^2)，1e6 时是 1e12，必挂。 Manacher 靠「已经算出的最右回文区间 [l, r]」做镜像预测：若当前中心 i < r，则 p[i] 至少是 min(r - i, p[mirror])，从这个下界继续扩即可，整体均摊 O(n)。

奇偶统一的技巧：在每两个字符之间以及首尾插入分隔符 '#'，得到长度 2n+1 的新串 t。t 中每个位置的回文半径 p[i] 恰好等于原串中对应回文子串的长度（这是插入 '#' 的漂亮之处：原长 L 的回文在 t 中半径就是 L，奇偶都不用分类讨论）。所以答案就是 max(p)。

数据规模与复杂度¶

n <= 1e6 -> t 长 2e6+1，O(n)。

Python 的坑（本题必看）¶

构造 t 用 bytearray + 切片赋值： t = bytearray(b'#' * (2n+1)); t[1::2] = s 这比 '#'.join(s) 之类快得多，而且后续索引拿到的是 int，比较更快；
内层的 while 扩展循环要尽量精简：把 t、p 绑成局部变量，边界判断合并成一次比较（这里在 t 两端各留一个哨兵位，用不同的字符保证扩展一定会停下来，从而省掉两次下标越界检查）；
一次性 read + 一次 write，不用 input()。

坑在哪¶

读入的一行字符串要用 split() 取第一个 token（顺带去掉换行 / 回车）；
p[i] 的初值必须是 min(r - i, p[2*c - i])，忘了和 r - i 取 min 会越过已知区间导致错误；
更新最右区间时用 i + p[i] > r 判断，并同时更新中心 c。

参考实现¶

solutions/nowcoder/BISHI94/sol.py
import sys


def main() -> None:
    s = sys.stdin.buffer.read().split()[0]      # split() 顺带剥掉行尾的换行 / 回车
    n = len(s)
    # t = ^ # s0 # s1 # ... # $，两端哨兵保证扩展循环自然停止
    m = 2 * n + 1                               # 插入分隔符后的有效长度（不含两端哨兵）
    t = bytearray(b'^' + b'#' * m + b'$')       # 总长 2n+3，t[0] 与 t[2n+2] 是哨兵
    # 切片起止：从 2 开始、到 2n+2 前止、步长 2，恰好 n 个位置。
    # t[0] 是左哨兵、t[1] 是第一个分隔符，所以原串第 j 个字符落在 t[2+2j]
    t[2:2 + 2 * n:2] = s                        # 原字符落在 t 的偶数下标上

    # 主循环维护三样东西：每个中心的回文半径 p、当前右端最靠右的那个回文 (c, r)，
    # 以及答案 best。p 开到 m + 2 是为了让哨兵位也有合法下标，省掉边界判断
    p = [0] * (m + 2)                           # p[i] = t 中以 i 为中心的回文半径
    c = r = 0                                   # c 是已知最右回文的中心，r 是其右端
    best = 0
    for i in range(1, m + 1):                   # 从 1 开始，跳过左哨兵
        # 镜像预测省掉重复扩展：i 还在已知回文内时，它的镜像点已经算过，
        # 那个半径可以白拿；但只能用到 r 为止——超出 r 的部分不在已知回文的
        # 覆盖范围内，对称性给不出保证，必须老实往外扩
        if i < r:
            mir = 2 * c - i                     # i 关于中心 c 的镜像位置
            k = r - i
            pm = p[mir]
            k = pm if pm < k else k             # 下界 = min(右边界剩余, 镜像半径)
        else:
            k = 0                               # 落在已知区间之外，只能从零开始扩
        while t[i - k - 1] == t[i + k + 1]:     # 哨兵 ^ / $ 保证一定会失配停下
            k += 1
        p[i] = k
        if i + k > r:                           # 扩出了更靠右的回文，换一个参照中心
            c, r = i, i + k
        if k > best:                            # 半径即原串中的回文长度，直接打擂台
            best = k
    sys.stdout.write("%d\n" % best)


main()

BISHI94 【模板】马拉车算法¶