CF1827C Palindrome Partition 题解

题面

题目传送门。

称一个字符串是好的，当且仅当它是一个长度为偶数的回文串或由若干长度为偶数的回文串拼接而成。

给定一个长度为 \(n\) 的字符串 \(s\)，求有多少 \(s\) 的子串是好的。

$ 1 \le n \le 5 \cdot 10^5\(，\)s$ 仅包含小写字母。

与 CSP-S 2023 T2 的区别

千万不要说这两题重了，免得别人来笑话。

举一个例子，abbcca，可以思考一下。

分析

那么这题多半是只能老老实实去找回文串。考虑使用回文树。

先来分析回文串的性质。

• 设 \(s[l,r]\) 为回文串，若 \(s[x,r]\) 也为回文串（\(\left\lfloor \frac{l+r+1}{2}\right\rfloor \le x \le r\)）。
• 则 \(s[l,l+(r-x+1)-1]\) 也为回文串（因为整体回文，所以右边会问则左边也回文）。
• 则 \(s[l+(r-x+1),x-1]\) 也为回文串（因为整体回文）。

如果通过第一个假设，判断 \(s[l,r]\) 是好的就不需要判断 \(s[l,r]\) 是否回文，只用判断它内部是否可以组成。

思路

我们知道在字符串位置 \(i\)，在回文树位置 \(j\)，只用不断跳后缀链接，设当前位置回文串的长度为 \(l\)，则 \(s[i-l+1,i]\) 为回文串。

设对于所有 \(l\) 为偶数，组成一个序列 \(L_1<L_2<L_3<\cdots<L_k\)，那么 \(s[i-L_x+1,i]\) （\(2 \le x \le k\)）必定可以被除自己的回文串组成（通过分析容易知道）。

那么我们只用对于每个 \(i\) 找到 \(L_1\)（可以用路径压缩来解决满足复杂度要求），则 \(dp_i=dp_{L_1}+1\)，若没有 \(L_1\)，则 \(dp_i=0\)。

最后答案为 \(\sum_{x=1}^{n}{dp_x}\)。

时间复杂度 \(O(n \log n)\)，瓶颈在找到 \(L_1\)。

Code

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using Pair = pair<LL, LL>;

const int MAXN = 1e6 + 3;

int n;
string s;
int trie[MAXN][26], cv = 1, len[MAXN], _len[MAXN], pos[MAXN]/*原串中出现位置*/, nxt[MAXN]/*后缀链接*/;
int fa[MAXN];
LL dp[MAXN], ans = 0;

int Getf(int x){
  if(fa[x] <= 1|| fa[x] == x || Getf(fa[x]) == 0 || _len[Getf(fa[x])] == 0){
    return (len[x] % 2 == 0 ? fa[x] = x : fa[x] = 0);
  }else return fa[x] = Getf(fa[x]);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--){
    cin >> n >> s, s = " " + s;
    for(int i = 0; i <= cv; i++){
      for(int col = 0; col < 26; col++) trie[i][col] = 0;
    }
    cv = 1;
    ans = 0;
    _len[0] = len[0] = -1, nxt[0] = 0, _len[1] = len[1] = 0, nxt[1] = 0;
    for(int i = 1, j = 1 /* i-1 的后缀的最长回文后缀对应回文树上的节点编号 */; i <= n; i++){
      while(s[i] != s[i - len[j] - 1]) j = nxt[j];
      if(!trie[j][s[i] - 'a']){
        trie[j][s[i] - 'a'] = ++cv;
        _len[cv] = len[cv] = len[j] + 2;
        pos[cv] = i - len[cv] + 1;
        for(int &k = (nxt[cv] = nxt[j]); s[i] != s[i - len[k] - 1]; k = nxt[k]);
        // 也可以写成 for(int &k = nxt[cv] = nxt[j]; s[i] != s[i - len[k] - 1]; k = nxt[k]);

        if(len[cv] > 1) fa[cv] = nxt[cv] = trie[nxt[cv]][s[i] - 'a'];
        else fa[cv] = nxt[cv] = 1;
      }
      j = trie[j][s[i] - 'a'];
      if(Getf(j) != 0) _len[j] = _len[Getf(j)];
      else _len[j] = 0;
      dp[i] = (_len[j] == 0 ? 0 : dp[i - _len[j]] + 1), ans += dp[i];
    }
    cout << ans << "\n";
  }
  return 0;
}
/*
6
abaaba
1 2 1 1 1
1 2 0 1 1**
2 3 1 1 1
2 3 0 1 1**
3 4 2 2 3
3 4 0 2 3**
4 5 2 2 2
*/