一类使用回文自动机优化的动规问题

本文主要讲述了一类回文子串划分问题的高效率解法，基于$3$年前adamant的一篇文章讨论。

阅读本文需要有回文自动机的基础。
本文中记$s^T$为字符串$s$的翻转串，$\left|s\right|$为字符串$s$的长度。

问题描述

给定一个长度为$n$的字符串，将其中若干个位置断开，要求每个分割出来的串都满足回文，询问最少需要断开几次。
$n\le10^5$

暴力

可以使用Manacher或Hash，设$f(i)$为对于前缀$1\rightarrow i$的答案，不难设计出一个$O(n^2)$的动规。

加入回文自动机

既然本文称作一类使用回文自动机优化的动规问题，那么考虑使用回文自动机呢？
对于每一个前缀，处理好其回文自动机，接下来在$last$的$fail$链进行转移即可。
这样的转移仍然是$O(n^2)$的，在数据随机的情况下可以做到$O(n\alpha+n\log n)$。

优化

考虑什么情况可以优化，举个栗子来进行说明：

更形式化地：
在回文自动机上记录$diff(x)=len(x)-len(next(x))$，$snext(x)=y$表示$x$的$fail$链上距离$x$最近的$y$满足$diff(y)\neq diff(x)$。
这两个属性都很好计算：

1 2	diff[now]=len[now]-len[next[now]]; snext[now]=diff[now]==diff[next[now]]?snext[next[now]]:next[now];

记$series(x)$表示$x\rightarrow snext(x)$的链（包含$x$，不含$snext(x)$），称作系列。

如图，蓝色数字表示$diff$，红色字符串表示结点对应回文串，相同颜色结点表示处于同一$series$中。

不难发现，对于同一$series$中的转移可以在$O(n)$时间内完成。
方法如下：
记当前前缀为$i$，转移中回文自动机结点为$v$，若$next(v)\in series(v)$，则从$next(v)$处继承前面的转移。然后计算出新的转移所在位置$i-(len[snext[v]]+diff[v])$，加入当前系列的转移，计算答案。
不断地让$v$在$fail$链上跳跃，即可考虑到所有转移。

代码如下：（使用series[]记录系列的转移最优值）

for(int i=1; i<=n; i++) {
	insert(s[i]-'a');
	for(int v=last; len[v]>0; v=snext[v]) {
		series[v]=f[i-(len[snext[v]]+diff[v])];
		if(diff[v]==diff[next[v]])series[v]=min(series[v],series[next[v]]);
		f[i]=min(f[i],series[v]+1);
	}
}

设$snext$指针所构成的树高为$T(n)$，显然时间复杂度为$O(nT(n))$。
下面我们证明$T(n)\le \log n$，也就是说该算法时间复杂度为$O(n\log n)$。

树高证明

原文章中给出过一个证明。
当然，因为我英语太渣了，看不懂（~~根本找不到证明的位置~~），因此在Cydiater的帮助下作出了如下证明：

给出一个结论：
对于一个结点$v$，若$2diff(v)\lt len(v)$，则其一定不是某个系列的上端点。
根据这个结论，系列上端点均满足$diff(v)\ge\frac{len(v)}2$，因此每次跳跃长度至少减少一半，则树高$\le\log n$。

现在我们转而证明上述结论。
假设回文自动机上有一个结点$v$，其满足$2diff(v)\lt len(v)$，记其对应回文串为$s$，$v$与$next(v)$的差异为字符串$A$。
根据条件，有$diff(v)\lt len-diff(v)$，故其$next(v)$包含$A^T$，则划分$s$为如下几部分：

考虑$s$的最长回文后缀，也就是$next(v)$表示的字符串，根据其对称轴，可以发现左侧必须有两个$A$串：

若$s$除去左侧的两个$A$串依然是一个回文串，则$diff(v)=diff(next(v))$，即$v$一定不是某个系列的上端点。
故现在转而证明$s$除去左侧的两个$A$串得到的串（记为$s-2A$）依然是一个回文串。

若$\left|C\right|\gt \left|A\right|$，即$\left|s\right|\gt4\left|A\right|$：
根据$s$的对称轴，又可以发现右侧也有两个$A^T$串。

以此类推，根据$s$与其最长回文后缀的两条对称轴构成的对称关系，问题可以归纳到$\left|C\right|\le \left|A\right|$的情况，若在$\left|C\right|\le \left|A\right|$时满足结论，则$\left|C\right|\gt \left|A\right|$时依然满足。
若$\left|C\right|\le \left|A\right|$且$\left|s\right|\ge 3\left|A\right|$，即$3\left|A\right|\le s\le4\left|A\right|$：
依然根据$s$的最长回文后缀的对称轴，将$A^T$对称到左边，得到下图：

根据$s$的对称轴，将$B$与$B^T$对称到左边，得到：

因此$A=BB^TDD^T$，代入到右侧的$A^T$可以得到：$S-2A=BB^TA^T=BB^TDD^TBB^T$，显然是一个回文串。
若$2diff(v)<len(v)$且$\left|s\right|\lt 3\left|A\right|$，即$2\left|A\right|\lt\left|s\right|\lt 3\left|A\right|$：

将$B$与$B^T$通过$s$最长回文后缀的对称轴对称到右边：

因此$A^T=DD^TBB^T$，故$A=BB^TDD^T$，因此：
$S-2A=BB^T$，显然是一个回文串。

Q.E.D

路终会有尽头，但视野总能看到更远的地方。