回文树

           
            
              
              
                #include &LTbits/stdc++.h>
using namespace std;
const int maxn = 300000 + 5;
namespace pam {
int sz, tot, last;
int cnt[maxn], ch[maxn][26], len[maxn], fail[maxn];
char s[maxn];
int node(int l) {  // 建立一个新节点，长度为 l
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = cnt[sz] = 0;
  return sz;
void clear() {  // 初始化
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
int getfail(int x) {  // 找后缀回文
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
void insert(char c) {  // 建树
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - 'a']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - 'a'];
    ch[now][c - 'a'] = x;
  last = ch[now][c - 'a'];
  cnt[last]++;
long long solve() {
  long long ans = 0;
  for (int i = sz; i >= 0; i--) {
    




    
cnt[fail[i]] += cnt[i];
  for (int i = 1; i <= sz; i++) {  // 更新答案
    ans = max(ans, 1ll * len[i] * cnt[i]);
  return ans;
}  // namespace pam
char s[maxn];
int main() {
  pam::clear();
  scanf("%s", s + 1);
  for (int i = 1; s[i]; i++) {
    pam::insert(s[i]);
  printf("%lld\n", pam::solve());
  return 0;

               

             

           
          

最小回文划分

给定一个字符串 $s(1\le |s| \le 10^5)$ ，求最小的，使得存在 $s_1,s_2,\dots,s_k$ ，满足 $s_i(1\le i \le k)$ 均为回文串，且 $s_1,s_2, \dots ,s_k$ 依次连接后得到的字符串等于。

考虑动态规划，记表示长度为的前缀的最小划分数，转移只需要枚举以第个字符结尾的所有回文串

dp[i]=1+\min_{ s[j+1..i] \text{ 为回文串} } dp[j]

由于一个字符串最多会有个回文子串，因此上述算法的时间复杂度为，无法接受，为了优化转移过程，下面给出一些引理。

记字符串长度为的前缀为，长度为的后缀为。

周期：若 $0< p \le |s|$ ， $\forall 1 \le i \le |s|-p,s[i]=s[i+p]$ ，就称是的周期。

border：若 $0 \le r < |s|$ ，，就称是的 border。

周期和 border 的关系：是的 border，当且仅当是的周期。

证明

若是的 border，那么，因此 $\forall 1\le i \le |t|, s[i]=s[|s|-|t|+i]$ ，所以就是的周期。

若为周期，则 $\forall 1 \le i \le |s|-(|s|-|t|)=|t|,s[i]=s[|s|-|t|+i]$ ，因此，所以是的 border。

引理一

是回文串的后缀，是的 border 当且仅当是回文串。

证明

对于 $1 \le i \le |t|$ ，由和为回文串，因此有，所以是的 border。

对于 $1 \le i \le |t|$ ，由是的 border，有，由是回文串，有，因此，所以是回文串。

下图中，相同颜色的位置表示字符对应相同。

引理二

是回文串的 border ( $|s|\le 2|t|$ )，是回文串当且仅当是回文串。

证明

若是回文串，由引理，也是回文串。

若是回文串，由是的 border，因此 $\forall 1 \le i \le |t|, s[i]=s[|s|-|t|+i]=s[|s|-i+1]$ ，因为 $|s| \le 2|t|$ ，所以也是回文串。

引理三

是回文串的 border，则是的周期，为的最小周期，当且仅当是的最长回文真后缀。

引理四

是一个回文串，是的最长回文真后缀，是的最长回文真后缀。令分别为满足的字符串，则有下面三条性质

$|u| \ge |v|$ ；
如果，那么；
如果，那么。

证明

由引理的推论，是的最小周期，是的最小周期。考虑反证法，假设，因为是的后缀，所以既是的周期，也是的周期，而是的最小周期，矛盾。所以 $|u| \ge |v|$ 。
因为是的 border，所以是的前缀，设字符串，满足（如下图所示），其中是的 border。考虑反证法，假设 $|u| \le |z|$ ，那么 $|zu| \le 2|z|$ ，所以由引理，是回文串，由引理，是的 border，又因为，所以，矛盾。所以。
都是的前缀，，所以。

推论

的所有回文后缀按照长度排序后，可以划分成 $\log |s|$ 段等差数列。

证明

设的所有回文后缀长度从小到大排序为 $l_1,l_2,\dots,l_k$ 。对于任意 $2 \le i \le k-1$ ，若 $l_{i}-l_{i-1}=l_{i+1}-l_{i}$ ，则 $l_{i-1},l_{i},l_{i+1}$ 构成一个等差数列。否则 $l_{i}-l_{i-1}\neq l_{i+1}-l_{i}$ ，由引理，有 $l_{i+1}-l_{i}>l_{i}-l_{i-1}$ ，且 $l_{i+1}-l_{i}>l_{i-1}$ ， $l_{i+1}>2l_{i-1}$ 。因此，若相邻两对回文后缀的长度之差发生变化，那么这个最大长度一定会相对于最小长度翻一倍。显然，长度翻倍最多只会发生 $O(\log |s|)$ 次，也就是的回文后缀长度可以划分成 $\log |s|$ 段等差数列。

该推论也可以通过使用弱周期引理，对的最长回文后缀的所有 border 按照长度分类， $x \in [2^0,2^1),[2^1,2^2),\dots,[2^k,n)$ ，考虑这 $\log |s|$ 组内每组的最长 border 进行证明。详细证明可以参考金策的《字符串算法选讲》和陈孙立的 2019 年 IOI 国家候选队论文《子串周期查询问题的相关算法及其应用》。

有了这个结论后，我们现在可以考虑如何优化的转移。

优化

回文树上的每个节点需要多维护两个信息，和。表示节点和所代表的回文串的长度差，即。表示一直沿着 fail 向上跳到第一个节点，使得 $diff[v] \neq diff[u]$ ，也就是所在等差数列中长度最小的那个节点。

根据上面证明的结论，如果使用指针向上跳的话，每向后填加一个字符，只需要向上跳 $O(\log |s|)$ 次。因此，可以考虑将一个等差数列表示的所有回文串的值之和（在原问题中指 $\min$ ），记录到最长的那一个回文串对应节点上。

表示所在等差数列的值之和，且是这个等差数列中长度最长的节点，则 $g[v]=\sum_{slink[x]=slink[v]} dp[i-len[x]]$ ，这里是当前枚举到的下标。

下面我们考虑如何更新数组和数组。以下图为例，假设当前枚举到第个字符，回文树上对应节点为。为橙色三个位置的值之和（最短的回文串算在下一个等差数列中）。上一次出现位置是（在处结束），包含的值是蓝色位置。因此，实际上等于和多出来一个位置的值之和，多出来的位置是。最后再用去更新，这部分等差数列的贡献就计算完毕了，不断跳，重复这个过程即可。具体实现方式可参考例题代码。

最后，上述做法的正确性依赖于：如果和属于同一个等差数列，那么上一次出现位置是。

证明

根据引理，是的 border，因此其在处出现。

假设在中的位置出现。由于和属于同一个等差数列，因此 $2|fail[x]| \ge x$ 。多余的和处的有交集，记交集为，设串满足。用类似引理的方式可以证明，是回文串，而的前缀也是回文串，这与是的最长回文前缀（后缀）矛盾。

例题： Codeforces 932G Palindrome Partition

给定一个字符串，要求将划分为 $t_1, t_2, \dots, t_k$ ，其中是偶数，且 $t_i=t_{k-i+1}$ ，求这样的划分方案数。

题解

构造字符串 $t= s[0]s[n - 1]s[1]s[n - 2]s[2]s[n - 3] \dots s[n / 2 - 1]s[n / 2]$ ，问题等价于求的偶回文划分方案数，把上面的转移方程改成求和形式并且只在偶数位置更新数组即可。时间复杂度 $O(n \log n)$ ，空间复杂度。

参考代码

           
            
              
              
                #include &LTbits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1000000 + 5;
int add(int x, int y) {
  x += y;
  return x >= mod ? x -= mod : x;
namespace pam {
int sz, tot, last;
int ch[maxn][26], len[maxn], fail[maxn];
int cnt[maxn], dep[maxn], dif[maxn], slink[maxn];
char s[maxn];
int node(int l)




    
 {  // 建立一个长度为 l 的新节点
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = 0;
  cnt[sz] = 0;
  dep[sz] = 0;
  return sz;
void clear() {  // 初始化
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
int getfail(int x) {  // 找到后缀回文
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
void insert(char c) {  // 建树
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - 'a']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - 'a'];
    dep[x] = dep[fail[x]] + 1;
    ch[now][c - 'a'] = x;
    dif[x] = len[x] - len[fail[x]];
    if (dif[x] == dif[fail[x]])
      slink[x] = slink[fail[x]];
      slink[x] = fail[x];
  last = ch[now][c - 'a'];
  cnt[last]++;
}  // namespace pam
using pam::dif;
using pam::fail;
using pam::len;
using pam::slink;
int n, dp[maxn], g[maxn];
char s[maxn], t[maxn];
int main() {
  pam::clear();
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1, j = 0; i <= n; i++) t[++j] = s[i], t[++j] = s[n - i + 1];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    pam::insert(t[i]);
    for (int x = pam::last; x > 1; x = slink[x]) {
      g[x] = dp[i - len[slink[x]] - dif[x]];
      if (dif[x] == dif[fail[x]]) g[x] = add(g[x], g[fail[x]]);
      if (i % 2 == 0) dp[i] = add(dp[i], g[x]);  // 在偶数位置更新 dp 数组

               

             

           
          