回文樹學習小結

最近突然撿起了好久不搞的字元串，研究了一下一直覺得很神奇的回文樹。

做了十來道題，現在做個小結，至于回文樹是什麼，随便百度就可以找到精彩的解說，偶就不在這裡獻醜了。

相比于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;