回文子串划分

这篇总结基本上就是这篇文章的翻译。

这是一种算法，可以在$O(n)$空间、$O(n\log n)$的时间内求出将一个字符串划分成若干个为回文的子串，最少需要的划分次数。

这个算法魔改一下，还可以求一个字符串划分成若干个回文子串的方案数。（就是CF932G）

---

这个算法是基于回文树的，沿用了回文树中的一些数组的定义。

算法中的一些定义

1.$diff$表示$i$和节点$fail[i]$表示的字符串的长度之差$diff[i]=len[i]-len[fail[i]]$
2.$fa$表示$fail$树上，从$i$到根的路径上深度最大的满足$diff[x]!=diff[i]$的$x$。

即：

diff[now]=len[now]-len[fail[now]];
fa[now]=(diff[now]==diff[fail[now]])?fa[fail[now]]:fail[now];

---

原理&&过程

引理1：$fa[i]$构成了一颗深度不超过$\log n$的树

这个引理是正确的，但是我不会证明 这里有一篇论文~~

引理2：加入插入了前$i$个字符，考虑回文树上的节点$last$的一个祖先$v$，假设它满足$fa[v]\not =fail[v]$。首先，$fail[v]$这个串一定在$[i-len[v]+1\cdots i-(len[v]-len[fail[v]])]$出现过，并且由于$diff[v]=diff[fail[v]]=\cdots $（构成了一个等差数列），转移$dp[i]$的时候，需要考虑的是$dp[i-len[v]],dp[i-len[fail[v]]],dp[i-len[fail[fail[v]]]]\cdots $，那么考虑第一段等差数列，除了$dp[i-len[fa[v]]-diff[v]]$之外，其他的位置都会在$dp[i-(len[v]-len[fail[v]])]$中被考虑过了。设$g[v]$表示回文树上节点$v$上一次被枚举到的时候贡献的答案，那么就有：

for(int i=1;i<=n;++i)
{
	PT.insert(str[i]-'a');
	for(int v=last;v;v=fa[v])
	{
		g[v]=dp[i-len[fa[v]]-diff[v]];
		if(diff[v]==diff[fail[v]]) g[v]=min(g[v]+g[fail[v]]);
		dp[i]=min(dp[i],g[v]+1);
	}
}

如果要求划分方案数的话魔改一下，把min改成累加就可以了。