寫(xiě)在前面

如果你會(huì)$SAM$，相信回文自動(dòng)機(jī)不會(huì)難懂。

如果你不會(huì)，你可以參考我的上一篇文章。

至少回文自動(dòng)機(jī)是治愈系的吧。

作用

回文自動(dòng)機(jī)，也叫回文樹(shù)，簡(jiǎn)稱(chēng)$PAM$實(shí)際上它既不是自動(dòng)機(jī)也不是樹(shù)

處理回文串的有力工具?？赏耆?span id="ze8trgl8bvbq" class="katex--inline">$Manacher$，就是會(huì)多個(gè)字符集。

算法流程

首先一個(gè)結(jié)論：往一個(gè)串末尾加入一個(gè)字符，最多會(huì)增加一個(gè)沒(méi)出現(xiàn)過(guò)的回文串。

證明：

假設(shè)出現(xiàn)了兩個(gè)之前沒(méi)有出現(xiàn)的，它們都是當(dāng)前串的后綴。

根據(jù)對(duì)稱(chēng)性，把短的關(guān)于長(zhǎng)的的中心作對(duì)稱(chēng)，得到一個(gè)相同的回文串，說(shuō)明已經(jīng)出現(xiàn)過(guò)了。

矛盾，所以最多出現(xiàn)一個(gè)。

這么說(shuō)，對(duì)于字符串$S$，本質(zhì)不同的回文串最多有$|S|$個(gè)。

于是可以每個(gè)狀態(tài)表示一個(gè)本質(zhì)相同的回文串。用$le{n}_i$表示狀態(tài)$i$表示的回文串的長(zhǎng)度。

考慮到回文串兩邊一樣的，定義轉(zhuǎn)移$c$表示當(dāng)前串左右各加上一個(gè)$c$

因?yàn)榉制婊匚暮团蓟匚?#xff0c;所以定義兩個(gè)初始節(jié)點(diǎn)$0,1$，其中$len[0]=0,len[1]=?1$（讓$len[1]=?1$可以說(shuō)是這個(gè)算法最妙的地方）

$0$表示偶回文，$1$表示奇回文。$?1$可以看做添加時(shí)吞掉一個(gè)字符。

類(lèi)比$AC$自動(dòng)機(jī)，定義$fail[i]$為這個(gè)回文串的最長(zhǎng)非自己的回文后綴（以下簡(jiǎn)稱(chēng)回文真后綴）。

強(qiáng)行讓$fail[0]=fail[1]=1$

實(shí)際上有個(gè)隱含條件：1的所有轉(zhuǎn)移都到0

接下來(lái)同樣考慮增量。

當(dāng)我們插入$S[i]$時(shí)，現(xiàn)在我們知道$S[i?1]$的所有回文后綴，要求$S[i]$的回文后綴。

我們可以從前一個(gè)點(diǎn)跳$fail$，如果到某個(gè)點(diǎn)$p$剛好可以前后接上$S[i]$,即$S[i?len[p]?1]=S[i]$，說(shuō)明有一個(gè)$p$到當(dāng)前點(diǎn)的轉(zhuǎn)移。

如果已經(jīng)有轉(zhuǎn)移了，說(shuō)明這個(gè)回文串出現(xiàn)過(guò)，直接退出。

接下來(lái)維護(hù)$fail$。我們發(fā)現(xiàn)最長(zhǎng)回文真后綴和它本身具有相同的性質(zhì)。

在之前的基礎(chǔ)上繼續(xù)跳就可以了。如果跳到某個(gè)$p$有$S[i]$的轉(zhuǎn)移，說(shuō)明$ch[p][S[i]]$是個(gè)回文后綴，連過(guò)去就可以了。

栗子：$AABA$

插入$A$

此時(shí)$len[1]=?1$的優(yōu)勢(shì)就體現(xiàn)出來(lái)了，因?yàn)閯偤檬?span id="ze8trgl8bvbq" class="katex--inline">$S[i]=S[i]$

插入$A$,依次跳到$0,1$

插入$B$

插入$A$

實(shí)現(xiàn)

第一步插入的時(shí)候由于一些玄學(xué)問(wèn)題，$p$的$fail$可能接到自己身上

解決策略是先把fail算出來(lái)，再接到之前的節(jié)點(diǎn)后面

剩下的就很容易了

代碼有點(diǎn)古怪，僅供參考

char s[MAXN]; int n; int ch[MAXN][26],fail[MAXN]; int len[MAXN]; int las=1,tot=1; void init() {len[1]=-1;fail[0]=fail[1]=1; } void insert(int i) {int p=las;while (s[i-len[p]-1]!=s[i]) p=fail[p];if (ch[p][s[i]-'a']) return (void)(las=ch[p][s[i]-'a']);int q=fail[p];while (s[i-len[q]-1]!=s[i]) q=fail[q];las=++tot;fail[las]=ch[q][s[i]-'a']; len[ch[p][s[i]-'a']=las]=len[p]+2; }

運(yùn)用

①每個(gè)點(diǎn)結(jié)尾的回文個(gè)數(shù)

即$fail$樹(shù)的深度

②本質(zhì)不同的回文個(gè)數(shù)

就是狀態(tài)數(shù)

好像只有這些……

想到再補(bǔ)吧

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的回文自动机：从入门到只会打板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。