回文树学习小结

最近突然捡起了好久不搞的字符串，研究了一下一直觉得很神奇的回文树。

做了十来道题，现在做个小结，至于回文树是什么，随便百度就可以找到精彩的解说，偶就不在这里献丑了。

相比于manacher，回文树要显得强大的多，同样是接近o(n)的复杂度，

回文树只需要多一点的空间，就可以实现许多用manacher实现起来非常复杂的功能。

并且就代码量而言，回文树也足够的简短，作为处理回文串的工具，实在是非常的美妙。

做了这么多回文树的题，可以发现几点回文树的妙用以及稍稍的优化策略。

大概有一下几点，

节点数减2是本质不同的回文子串数量。

统计全部回文子串可以考虑先记录每个点的cnt,到最后向拓扑排序一样往fail(后缀匹配失败指针)对应的节点累加。

如果在线统计的话，每个点的cnt可以代表该回文串对应的后缀回文子串的数量，然后动态加动态统计。

然后是动态在字符串末尾加入字母和删除的操作，因为回文树每次加入,改变的是last指针的位置，以及是否新加入一个节点,

可以另开一个last数组来保存之前的位置，以及一个flag数组来记录新加入的点和边，退回的时候还原last，并且删边删点即可。

还有另外一种前后都可以加字母的操作，这种的话就是为前后开两个last来记录位置，因为是回文串，所以左右是相同的，

那么fail指针是通用的，唯一的一个需要注意的地方是当整个串是回文的时候要把前后两个last合并在一起。

最后是另加新边的问题，目前只遇到过需要加一条half边的，也就是fail的一个变种，可以用类似方法构造。

有时候，回文树是没办法开出足够的数组来存边的，那么可以用链表来建边，以时间来换空间，其实相应的，该方法同样可以用于

ac自动机和后缀自动机，当然，既然可以用链表来存，那么同样的，平衡树其实要更好一些，不过这样问题就显得复杂一些了。

在hust上挂了一场test，上述的各种问题其中都可以见到，​​点我​​

稍微一提，关于回文，本人的一点想法，

上述的各种问题，其实相互之间都没有冲突，那么考虑一个这样的问题，

维护一个双端队列，每次可以加入和删除一个int范围的数字，询问当前状态下的回文子串数量（本质相同以及不同两种的）

这个问题相当于融合了上述的各种要点，如果操作次数达到1e6，那么问题就有些变态了。

不过如果能够掌握上述的内容，还是可以搞定的。估计代码要写个150行左右吧。

另一个问题是给出多个字符串，在给定一个匹配串，求匹配串和给出的多个字符串的最长公共回文子串。

这里，其实可以把回文树当做是ac自动机一样来用，同样有tire树和fail指针，那么稍作修改就可以了。

貌似目前还没有看到哪个oj有这两个问题，或者是我做题不够多吧。

struct linklist
{
  int nt[maxn], ft[maxn], u[maxn], v[maxn], sz;
  void clear() { sz = 0; }
  void clear(int x) { ft[x] = -1; }
  int get(int x, int y)
  { 
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (u[i] == y) return v[i];
    }
    return 0;
  }//返回next[x][y]
  void insert(int x, int y, int z)
  {
    u[sz] = y;  v[sz] = z;
    nt[sz] = ft[x]; ft[x] = sz++;
  }//相当于next[x][y]=z;
};

struct PalindromicTree
{
  const static int maxn = 2e5 + 10;//总大小
  linklist next;
  LL sz;  //节点个数
  int last[2], tot[2];  //前端和后端的指针，以及字符串的前后位置
  int fail[maxn], len[maxn], cnt[maxn]; //失配指针，节点代表的回文串长度，统计答案用数组
  char s[maxn];   //当前字符串数组
  void clear()
  {
    len[1] = -1; len[2] = 0;  //初始设定，两个根节点为1和2
    fail[1] = fail[2] = 1;  //失配指针指向1
    cnt[1] = cnt[2] = 0;    //初始为0
    last[0] = last[1] = (sz = 3) - 2;   //双端指针为-1起始为1节点
    tot[0] = (tot[1] = T - 1) + 1;    //两端设定长度为预计的长度
    next.clear();   next.clear(1);  next.clear(2);  //清空next数组
  }
  int Node(int length)
  {
    len[sz] = length;   //新建节点
        cnt[sz] = 1; 
    next.clear(sz);
    return sz++;
  }
  int getfail(int x, int k)
  {
    s[tot[0] - 1] = s[tot[1] + 1] = 0;    //保证之前的数据不影响现在
    while (s[tot[k]] != s[tot[k] + (k ? -1 : 1)*(len[x] + 1)]) x = fail[x];
    return x;
  }
  int add(char pos, int k)  //k表示类型，0为从前端插入，1为从后端插入
  {
    int x = (s[tot[k] += k ? 1 : -1] = pos) - 'a', y = getfail(last[k], k);
    if (!(last[k] = next.get(y, x)))
    {
      next.insert(y, x, last[k] = Node(len[y] + 2));
      fail[last[k]] = len[last[k]] == 1 ? 2 : next.get(getfail(fail[y], k), x);
      cnt[last[k]] += cnt[fail[last[k]]];
      if (len[last[k]] == tot[1] - tot[0] + 1) last[k ^ 1] = last[k];
    }
    return cnt[last[k]];
  }
}solve;