回文双子星

Manacher算法

$Manacher$算法能在线性的时间求得以每个位置为中心,能构成的最长回文串的半径

<!more>

Step

  1. 在所有空隙位置(包括首尾)插入一个原串中不会出现的符号,处理偶数长度回文串
  2. 维护$MaxRight$表示当前访问到的回文字串中右端点的$max$,$pos$表示$maxright$对应的回文串的对称轴位置
  3. 利用回文串的对称性进行扩展

notes

$O(n)$

回文自动机

分享到: