CF1827C Palindrome Partition
CF1827C Palindrome Partition
前言
一个下午和 jimmywang 大力发明未果，写题解以记之。
思路
首先考虑求出以每个位置结尾的不可分割的偶回文串，这样就可以从前往后转移，但如果同一个位置结尾的这样的串有很多，\(\text{dp}\) 的复杂度肯定炸。
但其实每个点结尾的不可分割的偶回文串只有一个。
证明：假设以 \(x\) 这个位置结尾存在第二短的不可分割的偶回文串。记第一短的不可分割的偶回文串为 \(A\)，第二短的为 \(B\), \(A\) 的左端点为 \(i\)，\(B\) 的对称中心的左侧点为 \(j\)。若 \(j < i\)，那么 \(B\) 形如 \(A+C+A\)，其中 \(C\) 也为偶回文串，与 \(B\) 是不可分割的矛盾。若 \(j \ge i\)，则 \(A\) 形如 \(D+E+D\)，其中 \(D\) 与 \(E\) 都是偶回文串，与 \(A\) 是不可分割的矛盾。故 \(B\) 不存在，以 \(x\) 结尾的不可分割的偶回文串只有一个，且是以 \(x\) 结尾的最短的偶回文串。
可以结合图理解一下：
那么每个点只可能由前面的一个点转移过来，\(\text{dp}\) 的复杂度是 \(O(n)\) 的。
只需要在合适的复杂度里找出以每个点为结尾的最短偶回文串即可。
众所周知，\(\text{Manachar}\) 算法可以在线性时间内求解每个回文中心往外扩展的最长回文串。但我们要求的是最短。所以一个叫做车拉马的算法诞生了
先把所有对称中心以及每个中心当前对应期望回文串长度放进一个 \(\text{pair}\) 里入队，依然考虑从每个对称中心往外扩，如果当前期望长度下是回文串且右端点没被标记过，那就标记右端点，并把期望长度加 \(2\) 继续入队，否则直接出队。由于每个右端点只能被标记一次，复杂度 \(O(n)\)。
非常的对啊
被轻松 \(\text{Hack}\) 了，例如在 \(\text{abbbba}\) 中，中间三个 \(\text{bb}\) 被标记完后就扩不到整个串了。
既然线性做不到，舍弃一点复杂度，多个 \(\log\) 也没事嘛
把yigeyi'ge