回文自動(dòng)機(jī)講解！http://blog.csdn.net/u013368721/article/details/42100363

pam上每個(gè)點(diǎn)代表本質(zhì)不同的回文子串。len(i)代表長(zhǎng)度，cnt(i)代表個(gè)數(shù)（要最后在fail樹上dp一遍方可）。

答案直接枚舉一遍結(jié)點(diǎn)，然后用len(i)*cnt(i)，取最大者即可。

回文自動(dòng)機(jī)是非常優(yōu)越的數(shù)據(jù)結(jié)構(gòu)，可惜比manacher多一個(gè)字符集的空間……

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 300010 #define MAXC 26 struct PAM{int next[MAXN][MAXC];//next指針，next指針和字典樹類似，指向的串為當(dāng)前串兩端加上同一個(gè)字符構(gòu)成int fail[MAXN];//fail指針，失配后跳轉(zhuǎn)到fail指針指向的節(jié)點(diǎn)int cnt[MAXN];int num[MAXN];int len[MAXN];//len[i]表示節(jié)點(diǎn)i表示的回文串的長(zhǎng)度int S[MAXN];//存放添加的字符int last;//指向上一個(gè)字符所在的節(jié)點(diǎn)，方便下一次addint n;//字符數(shù)組指針int p;//節(jié)點(diǎn)指針int newnode(int l){//新建節(jié)點(diǎn)for(int i=0;i<MAXC;++i){next[p][i]=0;}cnt[p]=0;num[p]=0;len[p]=l;return p++;}void init(){//初始化p=0;newnode(0);newnode(-1);last=n=0;S[n]=-1;//開(kāi)頭放一個(gè)字符集中沒(méi)有的字符，減少特判fail[0]=1;}int get_fail(int x){//和KMP一樣，失配后找一個(gè)盡量最長(zhǎng)的while (S[n-len[x]-1]!=S[n]){x=fail[x];}return x ;}void add(int c){c-='a';S[++n]=c;int cur=get_fail(last);//通過(guò)上一個(gè)回文串找這個(gè)回文串的匹配位置if (!next[cur][c]){//如果這個(gè)回文串沒(méi)有出現(xiàn)過(guò)，說(shuō)明出現(xiàn)了一個(gè)新的本質(zhì)不同的回文串int now=newnode(len[cur]+2);//新建節(jié)點(diǎn)fail[now]=next[get_fail(fail[cur])][c];//和AC自動(dòng)機(jī)一樣建立fail指針，以便失配后跳轉(zhuǎn) next[cur][c]=now;num[now]=num[fail[now]]+1;}last=next[cur][c];cnt[last]++;}void count(){//父親累加兒子的cnt，因?yàn)槿绻鹒ail[v]=u，則u一定是v的子回文串！for(int i=p-1;i>=0;--i){cnt[fail[i]]+=cnt[i];}} }pam; typedef long long ll; char s[MAXN]; int main(){int len;pam.init();scanf("%s",s+1);len=strlen(s+1);for(int i=1;i<=len;++i){pam.add(s[i]);}pam.count();ll ans=0;for(int i=2;i<pam.p;++i){ans=max(ans,(ll)pam.cnt[i]*pam.len[i]);}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/autsky-jadek/p/6935356.html

總結(jié)

以上是生活随笔為你收集整理的【回文自动机】bzoj3676 [Apio2014]回文串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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