1.回文樹的next[charset]指針：
b->aba
那么就這樣表示：b.next[a]=aba
當(dāng)然樹里面肯定不能存字符串，于是就直接用下標(biāo)標(biāo)號代替了
2.回文樹的fail指針：
跟ac自動機(jī)類似，fail指針指向當(dāng)前節(jié)點(diǎn)的最大回文后綴
沒有就指向根
3.回文樹的根
有2個(gè)根，一個(gè)單根就是往下連回文串長度為奇數(shù)的節(jié)點(diǎn)，本身長度為-1
還有個(gè)雙根就是往下連回文串長度為偶數(shù)的節(jié)點(diǎn)，本身長度為0
雙根的fail指向單根
當(dāng)然，也可以像manacher那樣，aab->&a&a&b&，這樣只用單根就是一棵樹了。
可以樹DP或者可持久化什么的。。。
4.回文樹節(jié)點(diǎn)的域
len->表示當(dāng)前節(jié)點(diǎn)回文串的長度，一般做回文串長度的題會用
cnt->表示當(dāng)前節(jié)點(diǎn)被插入過多少次，一般做計(jì)數(shù)類的題會用，一般需要配合count函數(shù)
代碼模板：

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=100005; const int N=26; struct Palindromic_Tree{int next[MAXN][N],fail[MAXN],cnt[MAXN],len[MAXN],S[MAXN],last,n,p;int newnode(int l){for(int i=0;i<N;++i)next[p][i]=0;cnt[p]=0;len[p]=l;return p++;}void init(){p=0;newnode(0);newnode(-1);last=0;n=0;S[n]=-1;fail[0]=1;}int getfail(int x){while(S[n-len[x]-1]!=S[n])x=fail[x];return x;}void insert(int c){c-='a';S[++n]=c;int cur=getfail(last);if(!next[cur][c]){int now=newnode(len[cur]+2);fail[now]=next[getfail(fail[cur])][c];next[cur][c]=now;}last=next[cur][c];++cnt[last];}void count(){for(int i=p-1;i>=0;--i)cnt[fail[i]]+=cnt[i];} }pt; char s[MAXN]; int main() {scanf("%s",s);int n=strlen(s);pt.init();for(int i=0;i<n;i++)pt.insert(s[i]);pt.count();for(int i=0;i<pt.p;++i)printf("%d\n",pt.cnt[i]); }

下面說說用這個(gè)模板怎么做回文樹的題：
1.最長回文子串

for(int i=0;i<pt.p;++i)ans=max(ans,pt.len[i]);

很簡單吧，如果要輸出的話還要保存插入進(jìn)去的字符的下標(biāo)。
但是一般用manacher寫這個(gè)題會更簡單。
2.求字符串中有多少個(gè)本質(zhì)不同的回文子串
例如abad，本質(zhì)不同的回文字串有：a，b，d，aba，共4個(gè)。

ans=pt.p-2;

很簡單吧，其實(shí)就是看看回文樹里面除了根以外有幾個(gè)節(jié)點(diǎn)。
3.對于一個(gè)空字符串s，每次在s末尾加上一個(gè)字符，對于每次操作，求字符串中有多少個(gè)本質(zhì)不同的回文子串
其實(shí)跟上面代碼一樣。。每插入一次就算一次ans。提出這個(gè)只是為了說明回文樹是動態(tài)的。當(dāng)然，如果這個(gè)s支持刪除操作那么應(yīng)該會用到可持久化回文樹。刪除就得回到之前的版本。
4.求字符串每個(gè)回文子串出現(xiàn)過多少次
例如abad，本質(zhì)不同的回文字串有：a，b，d，aba，共4個(gè)。
a出現(xiàn)過2次。
b出現(xiàn)過1次。
d出現(xiàn)過1次。
aba出現(xiàn)過1次。
終于用到cnt數(shù)組了。
上面那個(gè)模板其實(shí)就是解決這個(gè)問題的。
就是非常簡單的樹DP

void count() {for(int i=p-1;i>=0;--i)cnt[fail[i]]+=cnt[i]; }

因?yàn)閕這個(gè)節(jié)點(diǎn)的fail[i]就是i的最長回文后綴
假設(shè)i出現(xiàn)過cnt[i]次，那么fail[i]除了它自己出現(xiàn)cnt[fail[i]]次，還在i中出現(xiàn)了cnt[i]次。并且還要倒著從葉子節(jié)點(diǎn)往根推。
最后要輸出答案的話，一般還是要保存下標(biāo)
根據(jù)下標(biāo)和回文串長度來按題意順序輸出cnt
5.求字符串中回文串的個(gè)數(shù)
例如abad。a出現(xiàn)過2次。b出現(xiàn)過1次。d出現(xiàn)過1次。aba出現(xiàn)過1次。
因此回文串有5個(gè)。
可以發(fā)現(xiàn)的是，剛才的樹DP已經(jīng)推到根了，那么根的cnt值就是答案。因?yàn)閮蓚€(gè)根之間有fail關(guān)系所以輸出哪個(gè)根的cnt都可以。
6.求兩個(gè)字符串的公共回文串的個(gè)數(shù)(2014-2015 ACM-ICPC, Asia Xian Regional Contest)
建兩棵回文樹，分別insert兩個(gè)字符串。
然后分別從2個(gè)根開始沿著next數(shù)組下去dfs。
如果treea.next[cura][i] 和treeb.next[curb][i] 都存在
那么說明兩個(gè)字符串都有相同的回文串，于是

cura=treea.next[cura][i]; curb=treeb.next[curb][i]; ans+=treea.cnt[cura]*treeb.cnt[curb];

然后遞歸下一層dfs(cura,curb);。
如果treea.next[cura][i] 和treeb.next[curb][i] 有一個(gè)不存在就不往下dfs了。
7.BZOJ 2565 最長雙回文串
給出一個(gè)字符串，求所有子串中能分成前后兩個(gè)部分都是回文串最長的子串的長度。
問題實(shí)際上是求兩個(gè)這樣的數(shù)組left[]，right[]，分別表示以某位置結(jié)尾往左或往右最長的回文子串。
這個(gè)怎么搞？
就是給出一個(gè)空字符串s，每次往s的末尾加一個(gè)字符，然后查詢s里面包含末尾字符的最長的回文子串的長度。修改一下insert函數(shù)：

int insert(int c) {c-='a';S[++n]=c;int cur=getfail(last);if(!next[cur][c]){int now=newnode(len[cur]+2);fail[now]=next[getfail(fail[cur])][c];next[cur][c]=now;}last=next[cur][c];++cnt[last];return len[last]; }

insert函數(shù)的返回值就是要求的。
如果從左往右加字符，得到的結(jié)果就是left[]，如果從右往左加字符，得到的就是right[]。然后枚舉中間點(diǎn)，答案是left[i]+right[i]，就可以找最大值。
所以需要2棵回文樹（當(dāng)然一棵用完了初始化再用一次也可以的）。

轉(zhuǎn)載于:https://www.cnblogs.com/geng4512/p/5296880.html

總結(jié)

以上是生活随笔為你收集整理的回文树笔记(转自quack_quack)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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