P4555 Solution
双回文串的左右两半部分显然是互相独立的。
于是考虑求出 \(lm_i\) 表示以 \(i\) 结尾的最长回文子串长度，\(rm_i\) 表示以 \(i\) 开头的最长回文子串长度，最后扫一遍所有的分隔符求 \(lm+rm\) 的最大值即可。
考虑如何求 \(lm,rm\)。先用 manacher 拉出 \(p\)，那么可以利用 \(p\) 先进行一次更新：
\[lm_{i+p_i-1}\gets\max(lm_{i+p_i-1},p_i-1) \]\[rm_{i-p_i+1}\gets\max(rm_{i-p_i+1},p_i-1) \]这时候你发现我们只更新了最大值的部分。
例如 abcba 这个回文串我们只让 \(lm_5\) 对 \(5\) 取了最大值，让 \(rm_1\) 对 \(5\) 取了最大值。
我们可以考虑让 \(lm_5\) 的值倒着推回前面，更新前面的 \(lm\)。（\(rm\) 同理）
具体地，你发现 \(lm_4\) 可以取到 \(lm_5\) 的长度减去两端的两个 \(a\) 的贡献，也就是说我们有以下更新：
\[lm_i=\max(lm_i,lm_{i+2}-2) \]\[rm_i=\max(rm_i,rm_{i-2}-2) \]\(\pm2\) 的原因是我们只在分隔符之间转移。
复杂度 \(\mathcal O(n)\)。
标签：max,p4555,lm,solution,更新,rm,最大值,回文 From： https://www.cnblogs.com/iorit/p/18052646