題幹與適用場景
給定字元流 s[0..n)，每次只能追加一個字元。追加後要維護不同回文子字串數量、每個回文的出現次數，並回傳目前前綴的最長回文後綴。要求線上處理，不能每次重新列舉所有子字串。
回文樹（Eertree）為每個不同回文建立節點，邊表示兩側追加相同字元，suffix link 指向最長的真回文後綴。高品質回答要說明兩個特殊根、如何尋找可擴展的回文後綴，以及為何每次最多新增一個節點。
面試官考察點
- 能否正確區分長度
-1與長度0的兩個根。 - 是否理解
last、最長回文後綴與 suffix link 的意義。 - 能否追加字元時找到可擴展節點並建立轉移。
- 是否知道節點數、建構時間與空間上界都是
O(n)。 - 是否處理重複字元、空字串、字元集表示與計數傳播順序。
- 能否延伸到回文切分或滑動視窗變體。
回答前需要澄清的問題
- 輸入是一次性字串還是只能右端追加的串流？是否需要刪除左端？
- 出現次數按結束位置計數，還是要統計最終總出現次數？
- 字元集是小寫字母、Unicode，還是要支援任意整數 token？
- 需要回傳最長回文內容、節點編號，還是只要長度與計數？
- 是否要線上回答每個前綴的回文切分，或只維護 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 σ) 因子。