程式設計面試：如何用回文樹（Eertree）線上統計不同回文子字串？

題干與適用場景

給定字元流 s[0..n)，每次只能追加一個字元。追加後要維護不同回文子字串數量、每個回文的出現次數，並回傳目前前綴的最長回文後綴。要求線上處理，不能每次重新列舉所有子字串。

回文樹（Eertree）為每個不同回文建立節點，邊表示兩側追加相同字元，suffix link 指向最長的真回文後綴。高品質回答要說明兩個特殊根、如何尋找可擴展的回文後綴，以及為何每次最多新增一個節點。

面試官考察點

• 能否正確區分長度 -1 與長度 0 的兩個根。
• 是否理解 last、最長回文後綴與 suffix link 的意義。
• 能否追加字元時找到可擴展節點並建立轉移。
• 是否知道節點數、建構時間與空間上界都是 O(n)。
• 是否處理重複字元、空字串、字元集表示與計數傳播順序。
• 能否延伸到回文切分或滑動視窗變體。

回答前需要澄清的問題

1. 輸入是一次性字串還是只能右端追加的串流？是否需要刪除左端？
2. 出現次數按結束位置計數，還是要統計最終總出現次數？
3. 字元集是小寫字母、Unicode，還是要支援任意整數 token？
4. 需要回傳最長回文內容、節點編號，還是只要長度與計數？
5. 是否要線上回答每個前綴的回文切分，或只維護 distinct palindrome 集合？

30 秒回答框架

我維護兩個根：長度 -1 的奇根與長度 0 的偶根；每個普通節點保存回文長度、指向最長真回文後綴的 suffix link，以及按字元索引的轉移。last 表示目前前綴的最長回文後綴。追加字元 c 時沿 suffix link 跳轉，直到找到兩側都能放入 c 的節點；若沒有 c 轉移就新建節點，suffix link 由新回文的最長真回文後綴決定。每次最多新建一個節點，因此建構是 O(n)，節點計數沿 suffix link 逆序傳播後得到總出現次數。

分步驟深入解答

1. 兩個根與節點欄位

奇根長度為 -1，它可把任意字元視為兩側匹配的哨兵；偶根長度為 0，代表空回文。普通節點保存 len、link、next、occ 與一次代表性的結束位置。last 初始指向偶根。

2. 找到可擴展的後綴

追加字元 c 到位置 pos 後，從 last 檢查節點回文左側的字元是否等於 c。不相等就令 v = link[v] 繼續跳。第一次滿足條件的節點就是目前前綴可擴展的最長回文後綴。

while s[pos - 1 - len[v]] != c:
    v = link[v]

實作通常在字串前放一個不屬於字元集的哨兵，避免奇根檢查產生負索引。

3. 建立轉移與新節點

若 next[v][c] 已存在，它就是新的 last，只需把該節點的 occ 加一。否則建立長度 len[v] + 2 的節點並設定轉移。長度為 1 的節點 link 直接指向偶根；更長節點則從 link[v] 開始尋找可擴展後綴，再取其 next[c]。

4. 為什麼最多新增一個節點

追加一個字元後，所有新產生的回文都必須以此字元結尾。它們中只有最長者不是舊前綴的子字串，其餘新回文都是該最長回文 suffix link 鏈上的既有節點。因此每個位置最多建立一個不同回文節點，總節點數不超過 n + 2。

5. 出現次數傳播

線上階段可把每個位置的最長回文後綴節點 occ 加一。輸入結束後按節點長度由大到小處理，把 occ[v] 加到 occ[link[v]]，每個回文的 occ 就包含所有以它為後綴的更長回文出現次數。只要 distinct 數量時，直接回傳普通節點數。

6. 回文切分延伸

若要計算前綴最少回文切分，可在每個位置沿 last 的 suffix link 鏈列舉以此位置結尾的回文，再做 dp[pos] = min(dp[pos - len[v]] + 1)。朴素沿鏈可能退化為 O(n^2)；可用 series link 合併長度差相同的鏈段，需先依約束選擇實作。

7. 邊界、字元集與複雜度

空字串只有兩個根；重複字元會命中既有轉移，不能重複建點。小字元集可用定長陣列，空間為 O(n * alphabet)；大字元集應用雜湊表或有序映射，複雜度要寫成期望 O(n) 或 O(n log σ)。只追加模型下，建構時間為 O(n)（雜湊轉移按期望計），空間為 O(n) 加轉移儲存。

高品質示範回答

我會先確認輸入是右端追加、字元集與出現次數定義。結構有長度 -1 與 0 兩個根，普通節點代表不同回文，last 是目前前綴的最長回文後綴。追加 c 時沿 suffix link 找到能在兩側包住 c 的最長節點；若轉移不存在就建立 len + 2 的新節點。新節點長度為 1 時 link 指向偶根，否則從父節點 link 鏈尋找對應轉移。每個位置最多建立一個節點，所以建構與每次追加是線性攤銷；記錄每次 last 後按長度降序向 link 彙總，即可得到每個回文的總出現次數。

常見錯誤

• 只有一個空根 → 奇偶長度邊界無法統一 → 保留 -1 與 0 兩個根。
• 每次從根重新找後綴 → 失去線上線性性質 → 從 last 沿 suffix link 跳轉。
• 把 last 當最長回文子字串 → 它只保證是目前前綴的最長回文後綴。
• 新建節點後 link 指向父節點 → link 應指向最長真回文後綴節點。
• 每次把所有回文 occ 加一 → 會重複計數 → 先記錄結束位置，再逆序沿 link 傳播。
• 用固定小陣列處理任意 Unicode → 可能溢位或錯誤合併 → 先明確字元編碼與映射策略。

追問及應對

和 Manacher 演算法如何選擇？

Manacher 適合一次性求每個中心的最長回文半徑；Eertree 直接表示所有不同回文，天然支援線上追加、節點級計數與後綴鏈查詢。若需求只有靜態最長回文，Manacher 通常更簡單。

如何回傳目前最長回文內容？

節點保存任意一次結束位置 endPos，配合 len 從原字串切片即可。線上串流若不保留全部輸入，需要額外的環形快取或外部儲存。

為何統計每個回文出現次數要逆序傳播？

更長回文的每次出現也代表其 suffix link 回文出現一次。按長度由大到小傳播可保證子節點貢獻已彙總，再累加到父節點。

可以支援左端刪除嗎？

普通 Eertree 只支援右端追加。滑動視窗需要雙端回文樹或重建／分塊方案，選擇取決於視窗大小、刪除比例與延遲目標。

next 使用雜湊表會改變什麼？

雜湊表讓轉移查找為期望 O(1)，總體期望 O(n)；最壞情況取決於雜湊實作。若需要確定性邊界，可用有序映射並接受 O(log σ) 因子。