信奧新賽季進入沖刺階段字符串算法是各大省級、校級 C 上機賽的?？?。前面我們聊過后綴自動機、后綴數(shù)組、多模式串匹配今天把字符串四劍客的最后一位補齊——回文自動機Palindrome Automaton也叫回文樹 Eertree。它能在線性的時間里把字符串里所有的鏡像片段回文子串一次性梳理清楚本質(zhì)不同回文子串有多少個、最長的是多長、每個回文串出現(xiàn)了幾次。比起馬拉車Manacher只能求最長回文半徑回文自動機還多了一層計數(shù)的本領(lǐng)是處理回文統(tǒng)計類題目的利器。一、原創(chuàng)題校園廣播臺聽寫回文挑戰(zhàn)校園廣播臺每天播放一段由小寫字母組成的鏡像詩編輯想知道這段內(nèi)容里藏了多少個回文片段。給定字符串S僅含小寫字母|S| ≤ 10^5請回答三個問題問題一S中有多少個本質(zhì)不同的回文子串鏡像片段問題二其中最長的回文子串長度是多少問題三所有回文子串可重疊計數(shù)一共出現(xiàn)了多少次即回文子串的總數(shù)示例S ababa- 本質(zhì)不同回文子串a(chǎn)、b、aba、bab、ababa→5 個- 最長回文子串長度5- 回文子串總數(shù)a×3 b×2 aba×2 bab×1 ababa×1 9二、核心考點拆解回文自動機的精髓是建兩棵樹讓每個節(jié)點代表一個本質(zhì)不同的回文子串。雙根結(jié)構(gòu)維護兩個虛根——節(jié)點0是偶數(shù)長度回文的根len0節(jié)點1是奇數(shù)長度回文的根len-1。真實回文節(jié)點從2號開始因此本質(zhì)不同回文個數(shù) 節(jié)點總數(shù) ? 2。節(jié)點含義每個節(jié)點u存len[u]該回文長度、fail[u]最長真回文后綴指針類似后綴自動機的后綴鏈接、ch[u][c]在左右各加字符c后跳轉(zhuǎn)到的節(jié)點、cnt[u]出現(xiàn)次數(shù)。get_fail跳鏈給定當(dāng)前位置i和節(jié)點x沿fail向上跳直到S[i]與S[i ? len[x] ? 1]相等——也就是說x代表的回文串左右各加一個S[i]后仍是回文。extend增量插入逐字符插入。若ch[x][S[i]]已存在說明該回文早已建好僅把出現(xiàn)次數(shù)1否則新建節(jié)點len len[x] 2并算出它的fail。fail的計算新節(jié)點的fail指向去掉首尾字符后最長的回文后綴通過get_fail(fail[x], i)找到后再取其字符c的轉(zhuǎn)移單字符回文len1的fail固定指向偶根0空串。出現(xiàn)次數(shù)上推插入時只在以i結(jié)尾的最長回文節(jié)點上1構(gòu)建完成后按節(jié)點編號從大到小沿fail累加cnt[fail[u]] cnt[u]即可得到每個回文串的總出現(xiàn)次數(shù)——任何回文串的出現(xiàn)次數(shù)等于它作為后綴結(jié)尾的位置數(shù)。三、解法實現(xiàn)C / Python 雙版C 版本#include iostream #include string #include vector #include array #include algorithm using namespace std; struct PAM { int tot, last; vectorint len, fail, cnt; vectorarrayint, 26 ch; string s; void init() { tot 2; last 0; // 節(jié)點 0偶根(len0), 1奇根(len-1) len.assign({0, -1}); fail.assign({1, 0}); cnt.assign({0, 0}); ch.assign(2, arrayint, 26{}); // 兩個零填充數(shù)組 s.clear(); } int getfail(int x, int i) { while (i - len[x] - 1 0 || s[i - len[x] - 1] ! s[i]) x fail[x]; return x; } void extend(int c, int i) { int x getfail(last, i); if (ch[x][c]) { // 該回文已存在僅計一次出現(xiàn) last ch[x][c]; cnt[last]; return; } int cur tot; // 新建節(jié)點 len.push_back(len[x] 2); cnt.push_back(1); ch.push_back(arrayint, 26{}); if (len[cur] 1) // 單字符回文最長真后綴是空串偶根 fail.push_back(0); else { int y getfail(fail[x], i); fail.push_back(ch[y][c]); } ch[x][c] cur; last cur; } void build(const string str) { init(); for (int i 0; i (int)str.size(); i) { s str[i]; extend(str[i] - a, i); } } int distinct() { return tot - 2; } // 去掉兩個虛根 int longest() { int mx 0; for (int i 2; i tot; i) mx max(mx, len[i]); return mx; } long long total_occurrence() { // 沿 fail 把出現(xiàn)次數(shù)上推 for (int i tot - 1; i 2; --i) cnt[fail[i]] cnt[i]; long long sum 0; for (int i 2; i tot; i) sum cnt[i]; return sum; } }; int main() { PAM pam; string s ababa; pam.build(s); cout pam.distinct() pam.longest() pam.total_occurrence() \n; // 輸出5 5 9 return 0; }Python 版本class PAM: def __init__(self): self.len [0, -1] # 節(jié)點 0偶根, 1奇根 self.fail [1, 0] self.ch [dict(), dict()] self.cnt [0, 0] self.tot 2 # 下一個節(jié)點編號 self.last 0 self.s [] def get_fail(self, x, i): while i - self.len[x] - 1 0 or self.s[i - self.len[x] - 1] ! self.s[i]: x self.fail[x] return x def extend(self, c, i): x self.get_fail(self.last, i) if c in self.ch[x]: # 該回文已存在僅計一次出現(xiàn) self.last self.ch[x][c] self.cnt[self.last] 1 return cur self.tot self.tot 1 self.len.append(self.len[x] 2) self.cnt.append(1) self.ch.append(dict()) if self.len[cur] 1: # 單字符回文最長真后綴是空串 self.fail.append(0) else: y self.get_fail(self.fail[x], i) self.fail.append(self.ch[y][c]) self.ch[x][c] cur self.last cur def build(self, s): self.s list(s) for i, ch in enumerate(self.s): self.extend(ch, i) def distinct(self): return self.tot - 2 def longest(self): return max(self.len[2:]) if self.tot 2 else 0 def total_occurrence(self): # 沿 fail 上推出現(xiàn)次數(shù) for i in range(self.tot - 1, 1, -1): self.cnt[self.fail[i]] self.cnt[i] return sum(self.cnt[2:]) pam PAM() pam.build(ababa) print(pam.distinct(), pam.longest(), pam.total_occurrence()) # 5 5 9四、時間與空間復(fù)雜度時間復(fù)雜度get_fail沿fail跳鏈結(jié)合勢分析整個構(gòu)建過程是均攤O(n)的每個字符均攤常數(shù)步。total_occurrence的拓?fù)淅奂邮?O(節(jié)點數(shù)) O(n)。整體O(n)?？臻g復(fù)雜度本質(zhì)不同回文子串個數(shù)最多為 n 個每個節(jié)點存len/fail/cnt和 26 個轉(zhuǎn)移空間O(n·|Σ|)Σ 為字符集大小。字母表固定 26 時即 O(n)。五、六個高頻易錯點雙根初始化len必須是[0, -1]fail是[1, 0]tot從2起步。fail[0]1保證偶根跳空后落到奇根fail[1]0是奇根的兜底。get_fail的越界判斷i ? len[x] ? 1 0必須先判否則訪問s[-1]越界。這是回文自動機最常見的段錯誤來源。單字符回文的特殊faillen1的新節(jié)點fail要顯式指向 0偶根不能走通用公式否則會得到指向自身的錯誤后綴鏈接。fail拓?fù)漤樞虺霈F(xiàn)次數(shù)上推必須按節(jié)點編號從大到小遍歷fail[u] u恒成立從小到大會漏算。本質(zhì)不同回文個數(shù) tot ? 2兩個虛根不算真實回文千萬別漏減 2也不要把空串偶根算進去。字符集與數(shù)組大小用固定int ch[N][26]時要確保N足夠若圖省事用vector則天然無上限但要注意別把大數(shù)組塞進棧上分配會爆棧應(yīng)放在堆或全局。六、進階拓展每個回文串的出現(xiàn)次數(shù)total_occurrence執(zhí)行完后cnt[u]就是節(jié)點u代表回文的出現(xiàn)次數(shù)可直接回答某個回文出現(xiàn)了幾次。洛谷 P5496模板求以每個位置結(jié)尾的回文子串個數(shù)答案正是extend時當(dāng)前l(fā)ast節(jié)點被累加前的cnt值或構(gòu)建后再查cnt[last]。最長雙回文串洛谷 P4287對每個位置分別向左、向右求以該位置為對稱中心、作為左半或右半的最長回文拼接得到前后都是回文的最長串是fail樹與左右掃描的經(jīng)典應(yīng)用。廣義回文自動機多串建樹時插入新串前要重置last并把s清空若兩串交界處出現(xiàn)重復(fù)回文需要小心處理cnt的歸屬。與馬拉車Manacher對比Manacher 用O(n)直接給出每個中心的最長回文半徑常數(shù)更小回文自動機的優(yōu)勢在于能計數(shù)本質(zhì)不同個數(shù)、每個回文出現(xiàn)次數(shù)二者互補按題目需求選用。七、小結(jié)與互動回文自動機用一個兩棵樹 后綴鏈接的優(yōu)雅結(jié)構(gòu)把回文子串的枚舉、去重、計數(shù)一次性在線性時間內(nèi)解決。記住三條主線雙根建樹、get_fail跳鏈找對稱位置、fail拓?fù)渖贤平y(tǒng)計次數(shù)再配合上面的六個易錯點就能穩(wěn)穩(wěn)拿下這類字符串題。你在校內(nèi) C 訓(xùn)練或模擬賽里做過哪些回文相關(guān)的題目是求最長回文、數(shù)回文個數(shù)還是雙回文拼接歡迎在評論區(qū)聊聊我們下一期可以繼續(xù)深挖回文自動機在本質(zhì)不同回文 × 出現(xiàn)次數(shù)上的變式題。 免費少兒編程資料夸克網(wǎng)盤領(lǐng)取以下資料來自夸克網(wǎng)盤分享點擊鏈接可直接保存若需在 App 內(nèi)打開也可復(fù)制下方明文鏈接全國青少年信息素養(yǎng)大賽復(fù)賽集訓(xùn)題目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素養(yǎng)-智能算法應(yīng)用挑戰(zhàn)賽-復(fù)賽初中組題目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背記手冊.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython課程https://pan.quark.cn/s/a94bf02d00c62024信息素養(yǎng)大賽圖形化復(fù)賽集訓(xùn)題答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份電子學(xué)會考級真題https://pan.quark.cn/s/4403c42289122025全國青少年信息素養(yǎng)大賽賽項說明https://pan.quark.cn/s/d9d0df4a9f29青少兒信息素養(yǎng)大賽編程資料https://pan.quark.cn/s/4ab6bd83be8a資料持續(xù)更新關(guān)注獲取最新分享。