迴文樹

定義

迴文樹（EER Tree，Palindromic Tree，也被稱為迴文自動機）是一種可以存儲一個串中所有迴文子串的高效數據結構。最初由 Mikhail Rubinchik 和 Arseny M. Shur 在 2015 年發表。它的靈感來源於後綴樹等字符串後綴數據結構，使用迴文樹可以簡單高效地解決一系列涉及迴文串的問題。

結構

迴文樹大概長這樣

和其它自動機類似的，迴文樹也是由轉移邊和後綴鏈接（fail 指針）組成，每個節點都可以代表一個迴文子串。

因為迴文串長度分為奇數和偶數，我們可以像 manacher 那樣加入一個不在字符集中的字符（如 '#'）作為分隔符來將所有迴文串的長度都變為奇數，但是這樣過於麻煩了。有沒有更好的辦法呢？

答案自然是有。更好的辦法就是建兩棵樹，一棵樹中的節點對應的迴文子串長度均為奇數，另一棵樹中的節點對應的迴文子串長度均為偶數。

和其它的自動機一樣，一個節點的 fail 指針指向的是這個節點所代表的迴文串的最長迴文後綴所對應的節點，但是轉移邊並非代表在原節點代表的迴文串後加一個字符，而是表示在原節點代表的迴文串前後各加一個相同的字符（不難理解，因為要保證存的是迴文串）。

我們還需要在每個節點上維護此節點對應迴文子串的長度 len，這個信息保證了我們可以輕鬆地構造出迴文樹。

建造

迴文樹有兩個初始狀態，分別代表長度為 \(-1,0\) 的迴文串。我們可以稱它們為奇根，偶根。它們不表示任何實際的字符串，僅作為初始狀態存在，這與其他自動機的根節點是異曲同工的。

偶根的 fail 指針指向奇根，而我們並不關心奇根的 fail 指針，因為奇根不可能失配（奇根轉移出的下一個狀態長度為 \(1\)，即單個字符。一定是迴文子串）

類似後綴自動機，我們增量構造迴文樹。

考慮構造完前 \(p-1\) 個字符的迴文樹後，向自動機中添加在原串裏位置為 \(p\) 的字符。

我們從以上一個字符結尾的最長迴文子串對應的節點開始，不斷沿着 fail 指針走，直到找到一個節點滿足 \(s_{p}=s_{p-len-1}\)，即滿足此節點所對應迴文子串的上一個字符與待添加字符相同。

這裏貼出論文中的那張圖

我們通過跳 fail 指針找到 A 所對應的節點，然後兩邊添加 X 就到了現在的迴文串了（即 XAX），很顯然，這個節點就是以 \(p\) 結尾的最長迴文子串對應的樹上節點。（同時，這個時候長度 \(-1\) 節點優勢出來了，如果沒有 X 能匹配條件就是同一個位置的 \(s_p=s_p\)，就自然得到了代表字符 X 的節點。）此時要判斷一下：沒有這個節點，就需要新建。

然後我們還需要求出新建的節點的 fail 指針。具體方法與上面的過程類似，不斷跳轉 fail 指針，從 A 出發，即可找到 XAX 的最長迴文後綴 XBX，將對應節點設為 fail 指針所指的對象即可。

顯然，這個節點是不需新建的，A 的前 \(len_B\) 位和後 \(len_B\) 位相同，都是 B，前 \(len_B\) 位的兩端根據迴文串對應關係，都是 X，後面被欽定了是 X，於是這個節點 XBX 肯定已經被包含了。

如果 fail 沒匹配到，那麼將它連向長度為 \(0\) 的那個節點，顯然這是可行的（因為這是所有節點的後綴）。

線性狀態數證明

定理

對於一個字符串 \(s\)，它的本質不同迴文子串個數最多隻有 \(|s|\) 個。

證明

考慮使用數學歸納法。

當 \(|s| =1\) 時，\(s\) 只有一個字符，同時也只有一個子串，並且這個子串是迴文的，因此結論成立。
當 \(|s| >1\) 時，設 \(t=sc\)，其中 \(t\) 表示 \(s\) 最後增加一個字符 \(c\) 後形成的字符串，假設結論對 \(s\) 串成立。考慮以最後一個字符 \(c\) 結尾的迴文子串，假設它們的左端點由小到大排序為 \(l_1,l_2,\dots,l_k\)。由於 \(t[l_1..|t|]\) 是迴文串，因此對於所有位置 \(l_1 \le p \le |t|\)，有 \(t[p..|t|]=t[l_1..l_1+|t|-p]\)。所以，對於 \(1 < i \le k\)，\(t[l_i..|t|]\) 已經在 \(t[1..|t|-1]\) 中出現過。因此，每次增加一個字符，本質不同的迴文子串個數最多增加 \(1\) 個。

由數學歸納法，可知該定理成立。

因此迴文樹狀態數是 \(O(|s|)\) 的。對於每一個狀態，它實際只代表一個本質不同的迴文子串，即轉移到該節點的狀態唯一，因此總轉移數也是 \(O(|s|)\) 的。

正確性證明

以上圖為例，增加當前字符 X，由線性狀態數的證明，我們只需要找到包含最後一個字符 X 的最長迴文後綴，也就是 XAX。繼續尋找 XAX 的最長迴文後綴 XBX，建立後綴鏈接。XBX 對應狀態已經在迴文樹中出現，包含最後一個字符的迴文後綴就是 XAX，XBX 本身及其對應狀態在 fail 樹上的所有祖先。

對於 \(s\) 迴文樹的構造，令 \(n=|s|\)，顯然除了跳 fail 指針的其他操作都是 \(O(n)\) 的。

加入字符時，在上一次的基礎上，每次跳 fail 後對應節點在 fail 樹的深度 \(-1\)，而連接 fail 後，僅為深度 + 1（但 fail 為 \(0\) 時（即到 \(-1\) 才符合），深度相當於在 \(-1\) 的基礎上 \(+2\)）。

因為只加入 \(n\) 個字符，所以只會加 \(n\) 次深度，最多也只會跳 \(2n\) 次 fail。

因此，構造 \(s\) 的迴文樹的時間複雜度是 \(O(|s|)\)。

應用

本質不同迴文子串個數

由線性狀態數的證明，容易知道一個串的本質不同迴文子串個數等於迴文樹的狀態數（排除奇根和偶根兩個狀態）。

迴文子串出現次數

建出迴文樹，使用類似後綴自動機統計出現次數的方法。

由於迴文樹的構造過程中，節點本身就是按照拓撲序插入，因此只需要逆序枚舉所有狀態，將當前狀態的出現次數加到其 fail 指針對應狀態的出現次數上即可。

例題：「APIO2014」迴文串

定義 \(s\) 的一個子串的存在值為這個子串在 \(s\) 中出現的次數乘以這個子串的長度。對於給定的字符串 \(s\)，求所有迴文子串中的最大存在值。

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000 + 5;

namespace pam {
int sz, tot, last;
int cnt[maxn], ch[maxn][26], len[maxn], fail[maxn];
char s[maxn];

int node(int l) {  // 建立一个新节点，长度为 l
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = cnt[sz] = 0;
  return sz;
}

void clear() {  // 初始化
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
}

int getfail(int x) {  // 找后缀回文
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
}

void insert(char c) {  // 建树
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - 'a']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - 'a'];
    ch[now][c - 'a'] = x;
  }
  last = ch[now][c - 'a'];
  cnt[last]++;
}

long long solve() {
  long long ans = 0;
  for (int i = sz; i >= 0; i--) {
    cnt[fail[i]] += cnt[i];
  }
  for (int i = 1; i <= sz; i++) {  // 更新答案
    ans = max(ans, 1ll * len[i] * cnt[i]);
  }
  return ans;
}
}  // namespace pam

char s[maxn];

int main() {
  pam::clear();
  scanf("%s", s + 1);
  for (int i = 1; s[i]; i++) {
    pam::insert(s[i]);
  }
  printf("%lld\n", pam::solve());
  return 0;
}

最小回文劃分

給定一個字符串 \(s(1\le |s| \le 10^5)\)，求最小的 \(k\)，使得存在 \(s_1,s_2,\dots,s_k\)，滿足 \(s_i(1\le i \le k)\) 均為迴文串，且 \(s_1,s_2, \dots ,s_k\) 依次連接後得到的字符串等於 \(s\)。

考慮動態規劃，記 \(dp[i]\) 表示 \(s\) 長度為 \(i\) 的前綴的最小劃分數，轉移只需要枚舉以第 \(i\) 個字符結尾的所有迴文串

\[ dp[i]=1+\min_{ s[j+1..i] \text{ 為迴文串} } dp[j] \]

由於一個字符串最多會有 \(O(n^2)\) 個迴文子串，因此上述算法的時間複雜度為 \(O(n^2)\)，無法接受，為了優化轉移過程，下面給出一些引理。

記字符串 \(s\) 長度為 \(i\) 的前綴為 \(pre(s,i)\)，長度為 \(i\) 的後綴為 \(suf(s,i)\)。

週期：若 \(0< p \le |s|\)，\(\forall 1 \le i \le |s|-p,s[i]=s[i+p]\)，就稱 \(p\) 是 \(s\) 的週期。

border：若 \(0 \le r < |s|\)，\(pre(s,r)=suf(s,r)\)，就稱 \(pre(s,r)\) 是 \(s\) 的 border。

週期和 border 的關係：\(t\) 是 \(s\) 的 border，當且僅當 \(|s|-|t|\) 是 \(s\) 的週期。

證明

若 \(t\) 是 \(s\) 的 border，那麼 \(pre(s,|t|)=suf(s,|t|)\)，因此 \(\forall 1\le i \le |t|, s[i]=s[|s|-|t|+i]\)，所以 \(|s|-|t|\) 就是 \(s\) 的週期。

若 \(|s|-|t|\) 為 \(s\) 週期，則 \(\forall 1 \le i \le |s|-(|s|-|t|)=|t|,s[i]=s[|s|-|t|+i]\)，因此 \(pre(s,|t|)=suf(s,|t|)\)，所以 \(t\) 是 \(s\) 的 border。

引理一

\(t\) 是迴文串 \(s\) 的後綴，\(t\) 是 \(s\) 的 border 當且僅當 \(t\) 是迴文串。

證明

對於 \(1 \le i \le |t|\)，由 \(s\) 和 \(t\) 為迴文串，因此有 \(s[i]=s[|s|-i+1]=s[|s|-|t|+i]\)，所以 \(t\) 是 \(s\) 的 border。

對於 \(1 \le i \le |t|\)，由 \(t\) 是 \(s\) 的 border，有 \(s[i]=s[|s|-|t|+i]\)，由 \(s\) 是迴文串，有 \(s[i]=s[|s|-i+1]\)，因此 \(s[|s|-i+1]=s[|s|-|t|+i]\)，所以 \(t\) 是迴文串。

下圖中，相同顏色的位置表示字符對應相同。

引理二

\(t\) 是串 \(s\) 的 border (\(|s|\le 2|t|\))，\(s\) 是迴文串當且僅當 \(t\) 是迴文串。

證明

若 \(s\) 是迴文串，由引理 \(1\)，\(t\) 也是迴文串。

若 \(t\) 是迴文串，由 \(t\) 是 \(s\) 的 border，因此 \(\forall 1 \le i \le |t|, s[i]=s[|s|-|t|+i]=s[|s|-i+1]\)，因為 \(|s| \le 2|t|\)，所以 \(s\) 也是迴文串。

引理三

\(t\) 是迴文串 \(s\) 的 border，則 \(|s|-|t|\) 是 \(s\) 的週期，\(|s|-|t|\) 為 \(s\) 的最小週期，當且僅當 \(t\) 是 \(s\) 的最長迴文真後綴。

引理四

\(x\) 是一個迴文串，\(y\) 是 \(x\) 的最長迴文真後綴，\(z\) 是 \(y\) 的最長迴文真後綴。令 \(u,v\) 分別為滿足 \(x=uy,y=vz\) 的字符串，則有下面三條性質

\(|u| \ge |v|\)；
如果 \(|u| > |v|\)，那麼 \(|u| > |z|\)；
如果 \(|u| = |v|\)，那麼 \(u=v\)。

證明

由引理 \(3\) 的推論，\(|u|=|x|-|y|\) 是 \(x\) 的最小週期，\(|v|=|y|-|z|\) 是 \(y\) 的最小週期。考慮反證法，假設 \(|u| < |v|\)，因為 \(y\) 是 \(x\) 的後綴，所以 \(u\) 既是 \(x\) 的週期，也是 \(y\) 的週期，而 \(|v|\) 是 \(y\) 的最小週期，矛盾。所以 \(|u| \ge |v|\)。
因為 \(y\) 是 \(x\) 的 border，所以 \(v\) 是 \(x\) 的前綴，設字符串 \(w\)，滿足 \(x=vw\)（如下圖所示），其中 \(z\) 是 \(w\) 的 border。考慮反證法，假設 \(|u| \le |z|\)，那麼 \(|zu| \le 2|z|\)，所以由引理 \(2\)，\(w\) 是迴文串，由引理 \(1\)，\(w\) 是 \(x\) 的 border，又因為 \(|u| > |v|\)，所以 \(|w| > |y|\)，矛盾。所以 \(|u| > |z|\)。
\(u,v\) 都是 \(x\) 的前綴，\(|u|=|v|\)，所以 \(u=v\)。

推論

\(s\) 的所有迴文後綴按照長度排序後，可以劃分成 \(\log |s|\) 段等差數列。

證明

設 \(s\) 的所有迴文後綴長度從小到大排序為 \(l_1,l_2,\dots,l_k\)。對於任意 \(2 \le i \le k-1\)，若 \(l_{i}-l_{i-1}=l_{i+1}-l_{i}\)，則 \(l_{i-1},l_{i},l_{i+1}\) 構成一個等差數列。否則 \(l_{i}-l_{i-1}\neq l_{i+1}-l_{i}\)，由引理 \(4\)，有 \(l_{i+1}-l_{i}>l_{i}-l_{i-1}\)，且 \(l_{i+1}-l_{i}>l_{i-1}\)，\(l_{i+1}>2l_{i-1}\)。因此，若相鄰兩對迴文後綴的長度之差發生變化，那麼這個最大長度一定會相對於最小長度翻一倍。顯然，長度翻倍最多隻會發生 \(O(\log |s|)\) 次，也就是 \(s\) 的迴文後綴長度可以劃分成 \(\log |s|\) 段等差數列。

該推論也可以通過使用弱週期引理，對 \(s\) 的最長迴文後綴的所有 border 按照長度 \(x\) 分類，\(x \in [2^0,2^1),[2^1,2^2),\dots,[2^k,n)\)，考慮這 \(\log |s|\) 組內每組的最長 border 進行證明。詳細證明可以參考金策的《字符串算法選講》和陳孫立的 2019 年 IOI 國家候選隊論文《子串週期查詢問題的相關算法及其應用》。

有了這個結論後，我們現在可以考慮如何優化 \(dp\) 的轉移。

優化

迴文樹上的每個節點 \(u\) 需要多維護兩個信息，\(diff[u]\) 和 \(slink[u]\)。\(diff[u]\) 表示節點 \(u\) 和 \(fail[u]\) 所代表的迴文串的長度差，即 \(len[u]-len[fail[u]]\)。\(slink[u]\) 表示 \(u\) 一直沿着 fail 向上跳到第一個節點 \(v\)，使得 \(diff[v] \neq diff[u]\)，也就是 \(u\) 所在等差數列中長度最小的那個節點。

根據上面證明的結論，如果使用 \(slink\) 指針向上跳的話，每向後填加一個字符，只需要向上跳 \(O(\log |s|)\) 次。因此，可以考慮將一個等差數列表示的所有迴文串的 \(dp\) 值之和（在原問題中指 \(\min\)），記錄到最長的那一個迴文串對應節點上。

\(g[v]\) 表示 \(v\) 所在等差數列的 \(dp\) 值之和，且 \(v\) 是這個等差數列中長度最長的節點，則 \(g[v]=\sum_{slink[x]=slink[v]} dp[i-len[x]]\)，這裏 \(i\) 是當前枚舉到的下標。

下面我們考慮如何更新 \(g\) 數組和 \(dp\) 數組。以下圖為例，假設當前枚舉到第 \(i\) 個字符，迴文樹上對應節點為 \(x\)。\(g[x]\) 為橙色三個位置的 \(dp\) 值之和（最短的迴文串 \(slink[x]\) 算在下一個等差數列中）。\(fail[x]\) 上一次出現位置是 \(i-diff[x]\)（在 \(i-diff[x]\) 處結束），\(g[fail[x]]\) 包含的 \(dp\) 值是藍色位置。因此，\(g[x]\) 實際上等於 \(g[fail[x]]\) 和多出來一個位置的 \(dp\) 值之和，多出來的位置是 \(i-(len[slink[x]]+diff[x])\)。最後再用 \(g[x]\) 去更新 \(dp[i]\)，這部分等差數列的貢獻就計算完畢了，不斷跳 \(slink[x]\)，重複這個過程即可。具體實現方式可參考例題代碼。

最後，上述做法的正確性依賴於：如果 \(x\) 和 \(fail[x]\) 屬於同一個等差數列，那麼 \(fail[x]\) 上一次出現位置是 \(i-diff[x]\)。

證明

根據引理 \(1\)，\(fail[x]\) 是 \(x\) 的 border，因此其在 \(i-diff[x]\) 處出現。

假設 \(fail[x]\) 在 \((i-diff[x],i)\) 中的 \(j\) 位置出現。由於 \(x\) 和 \(fail[x]\) 屬於同一個等差數列，因此 \(2|fail[x]| \ge x\)。多餘的 \(fail[x]\) 和 \(i-diff[x]\) 處的 \(fail[x]\) 有交集，記交集為 \(w\)，設串 \(u\) 滿足 \(uw=fail[x]\)。用類似引理 \(1\) 的方式可以證明，\(w\) 是迴文串，而 \(x\) 的前綴 \(s[i-len[x]+1..j]=uwu\) 也是迴文串，這與 \(fail[x]\) 是 \(x\) 的最長迴文前綴（後綴）矛盾。

例題：Codeforces 932G Palindrome Partition

給定一個字符串 \(s\)，要求將 \(s\) 劃分為 \(t_1, t_2, \dots, t_k\)，其中 \(k\) 是偶數，且 \(t_i=t_{k-i+1}\)，求這樣的劃分方案數。

題解

構造字符串 \(t= s[0]s[n - 1]s[1]s[n - 2]s[2]s[n - 3] \dots s[n / 2 - 1]s[n / 2]\)，問題等價於求 \(t\) 的偶迴文劃分方案數，把上面的轉移方程改成求和形式並且只在偶數位置更新 \(dp\) 數組即可。時間複雜度 \(O(n \log n)\)，空間複雜度 \(O(n)\)。