Manacher 学习笔记

算法介绍

Manacher 算法是能在 O(n)O(n) 求解以每个位置为中心的最长回文子串长度的算法。

算法过程

在原字符串 ss 的两头分别加入不在字符集内的字符,比如 @\0,同时,在每相邻两个字符间加入不在字符集内的字符,比如 #,这样对于偶数长的回文子串也能像奇数长的回文子串一样处理。以此得到新字符串 ss' ,之后的操作均在 ss' 上。

定义 rightright 为已经算出来的所有回文子串中,右侧最远的一个的右侧端点,pospos 为其回文中心。

假设目前在考虑位置 ii ,记 j=2posij = 2 pos - i ,即 ii 关于 pospos 的对称点。分三种情况:

  • right<iright < i

    无特殊性质,ri1r_i \geqslant 1

  • righti,  jrj2posrightright \geqslant i, \; j - r_j \geqslant 2 pos - right

    rirjr_i \geqslant r_j

  • righti,  jrj<2posrightright \geqslant i, \; j - r_j < 2 pos - right

    rirightir_i \geqslant right - i

在由以上三种情况对应的最小值的基础上进行比较。

模版题

POJ 3974题解