洛谷 P4840 解题报告

STEP 1. 题目大意

• 求字符串 \(S\) 的所有循环同构中本质不同的回文子串数量的最大值。

• 数据范围 $ |S| \leq 1.5e6 $

STEP 2. 思路分析

看到回文串计数，首先肯定采用 \(PAM\) ，不妨设长度为 \(n\) ,

考虑将 \(S\) 倍长，这样原问题就转化为每一段长度为 \(n\) 的结束位置在后缀树上到根节点路径并的大小。

然而这样不是很好维护，于是我们考虑每次加入一个字符对答案区间贡献的范围，显然开始位置不能在当前回文串的中间某处。

于是在区间 \(\left[ i - n + 1, i - t[x].len + 1\right] \cup \left[ i + 1,n - 1\right]\) 中均可以取 （注意此处忽略了与 \(n\) 大小关系的分类讨论）。

但是如果每次暴力计算区间复杂度会炸，不过我们发现：

当我们把所有的可行区间合并在一起时，最终总区间不会多于 \(2\) 个。

这是因为每个回文子串至多被删除一次，然后又添加一次。

所以我们只需在回文树上暴力向父节点上传信息即可，注意上传时维护区间端点。

STEP 3. 复杂度分析

如果采用 \(\text {vector}\) 实现，并且即时更新区间，

复杂度为 \(O(|\Sigma| \times n) + O(n)\)

如果使用 \(\text {sort}\) ，那么复杂度为 \(O(|\Sigma| \times n) + O(n \times \log n)\)

不过众所周知 \(PAM\) 常数很大，所以得开 \(O2\) 。

STEP 4. 代码实现

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define Rep(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
const int maxN = 3000005;
int n, ans, tot = 1, in[maxN], d[maxN];
struct PAM {
  int ch[26], fail, len;
}t[maxN];
char s[maxN];
vector<pair<int, int> >vec[maxN];
queue<int> q;
int getf(int x, int pos) {
  while (pos - t[x].len - 1 < 0 || s[pos - t[x].len - 1] != s[pos]) x = t[x].fail;
  return x;
}
int main() {
  scanf("%s", s);
  n = strlen(s); t[0].fail = 1; t[1].len = -1;
  For (i, 0, n - 1) s[i + n] = s[i];
  int lst = 0;
  For (i, 0, n * 2 - 1) {
    int tr = getf(lst, i);
    if (!t[tr].ch[s[i] - 'a']) {
      ++tot; t[tot].fail = t[getf(t[tr].fail, i)].ch[s[i] - 'a'];
      t[tr].ch[s[i] - 'a'] = tot;
      t[tot].len = t[tr].len + 2;
      ++in[t[tot].fail];
    }
    lst = t[tr].ch[s[i] - 'a'];
    vec[lst].emplace_back(max(0, i - n + 1), min(i - t[lst].len + 1, n));
    vec[lst].emplace_back(i + 1, n - 1);
  } // PAM与区间更新
  For (i, 2, tot)
    if (!in[i]) q.emplace(i);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    sort(vec[x].begin(), vec[x].end());
    vector<pair<int, int> >nw;
    int ml = 0, mr = -1;
    for (auto s : vec[x]) {
      if (s.first > mr) {
        if (mr >= 0) nw.emplace_back(ml, mr);
        ml = s.first; mr = s.second;
      }
      mr = max(s.second, mr);
    }
    if (mr >= 0) nw.emplace_back(ml, mr); // 合并当前区间
    swap(nw, vec[x]);
    for (auto s : vec[x]) {
      if (t[x].len > 0 && t[x].len <= n) { 
        ++d[s.first]; --d[s.second + 1]; 
      } // 差分统计答案
      vec[t[x].fail].emplace_back(s.first, min(s.second - t[t[x].fail].len + t[x].len, n));
    }
    vec[x].clear(); vec[x].shrink_to_fit();
    if (!--in[t[x].fail]) q.emplace(t[x].fail);
  }
  int ans = d[0];
  For (i, 1, n - 1) {
    d[i] += d[i - 1];
    ans = max(ans, d[i]);
  }
  cout << ans;
  return 0;
}