WIKI

回文树

1. 效率高 时间复杂度 $O(n)$
2. 代码短
3. 支持在线查询和更新

前置知识

后缀 ->字符串从某个位置开始到末尾的子串

后缀链跳跃

1. 如果插入的字母形成 了新的 回文串 一定是 跟 前面的 后缀一起形成的
2. 若是 插入的 字母能形成 新 回文串 ，那么 对称位置一定有 相同的 字母
3. 在这两个 相同的 字母 之间 一定也是 一个 回文串
4. 插入 末尾后 从前面 尽量远的 地方开始 检查 （尽量远 但不能是 开头）

奇偶字典树

1. 用字典树 存储 回文串 （也是 后缀）
2. 回文串之间有 包含 关系
3. 用辅助数据定位到 新的 回文串 ，然后将新的回文串也 存储在字典树上

回文树 包括 奇偶 两种

从子节点 向上读到根 再从 根向下 读回到 子节点

如果是 一号根 靠近 1 的边读一次

如果是 零号根 靠近 0 的边读两次

回文树的边有两种

1. 带权有向边 ：用来表示 回文串
2. 后缀链 ： 无权边 ，连接两棵 字典树

Problem - 5421 (hdu.edu.cn)

code

#include <cstring>
#include <iostream>
using namespace std;
#define int long long
int n, m;
const int N = 3E5 + 10;
int s[N];
struct node {
  int fail, len, son[26], siz;
  void init(int _len) {
    memset(son, 0, sizeof son);
    fail = siz = 0;
    len = _len;
  }
} tr[N];
int num, last[2], ans, L, R;
void init() {
  last[0] = last[1] = 0;
  ans = 0, num = 1;
  L = 1E5 + 8, R = 1E5 + 7;
  tr[0].init(0);
  memset(s, -1, sizeof s);
  tr[1].init(-1);
  tr[0].fail = 1;
}
int getfail(int p, int d) {
  if (d)
    while (s[R - tr[p].len - 1] != s[R]) p = tr[p].fail;
  else
    while (s[L + tr[p].len + 1] != s[L]) p = tr[p].fail;
  return p;
}
void insert(int x, int d) {
  if (d)
    s[++R] = x;
  else
    s[--L] = x;
  int fa = getfail(last[d], d);
  int now = tr[fa].son[x];
  if (!now) {
    now = ++num;
    tr[now].init(tr[fa].len + 2);
    tr[now].fail = tr[getfail(tr[fa].fail, d)].son[x];
    tr[now].siz = tr[tr[now].fail].siz + 1;
    tr[fa].son[x] = now;
  }
  last[d] = now;
  if (R - L + 1 == tr[now].len) last[d ^ 1] = now;
  ans += tr[now].siz;
}
void solve() {
  while (cin >> n) {
    init();
    for (int i = 0; i < n; i++) {
      char c;
      cin >> c;
      if (c == '1') {
        cin >> c;
        insert(c - 'a', 0);
      } else if (c == '2') {
        cin >> c;
        insert(c - 'a', 1);
      } else if (c == '3')
        cout << num - 1 << "\n";
      else
        cout << ans << "\n";
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}