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