Manacher Algorithm

Longest palindrome subsequence

Dynamic Programming

\(O(n^2)\)

Manacher Algorithm

预处理

字符之间插入奇怪的符号

基础概念

• 回文半径数组 \(radius\)
• 最右回文右边界 \(R\)
  • 这个位置和它之前的回文子串到达的最右边的地方
• 最右回文右边界的对称中心 \(C\)

算法流程

第一种情况：下一个要移动的位置在 \(R\) 的右边

这时将移动的位置作为对称中心，向两边扩，更新上面那几个数组

第二种情况：下一个要移动的位置在 \(R\) 处或 \(R\) 的左边

先约定

• \(P_2\) 是 \(P_1\) 以 \(C\) 为对称中心的对称点
• \(P_L\) 是以 \(P_2\) 为对称中心的回文子串的左边界
• \(C_L\) 和 \(P_L\) 一个意思，以 \(C\) 为对称中心

分三种情况

• \(C_L < P_L\) 这时 \(P_1\) 的回文半径就是 \(P_2\) 的回文半径
• \(C_L = P_L\) 这时 \(P_1\) 的回文半径还要往外扩，但是只要从 \(R\) 之后往外扩就行了
• \(C_L > P_L\) 这时 \(P_1\) 的回文半径就是 \(P_1\) 到 \(R\) 的距离