首页 > 代码库 > 【回文自动机】bzoj3676 [Apio2014]回文串
【回文自动机】bzoj3676 [Apio2014]回文串
回文自动机讲解!http://blog.csdn.net/u013368721/article/details/42100363
pam上每个点代表本质不同的回文子串。len(i)代表长度,cnt(i)代表个数(要最后在fail树上dp一遍方可)。
答案直接枚举一遍结点,然后用len(i)*cnt(i),取最大者即可。
回文自动机是非常优越的数据结构,可惜比manacher多一个字符集的空间……
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 300010 #define MAXC 26 struct PAM{ int next[MAXN][MAXC];//next指针,next指针和字典树类似,指向的串为当前串两端加上同一个字符构成 int fail[MAXN];//fail指针,失配后跳转到fail指针指向的节点 int cnt[MAXN]; int num[MAXN]; int len[MAXN];//len[i]表示节点i表示的回文串的长度 int S[MAXN];//存放添加的字符 int last;//指向上一个字符所在的节点,方便下一次add int n;//字符数组指针 int p;//节点指针 int newnode(int l){//新建节点 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;//开头放一个字符集中没有的字符,减少特判 fail[0]=1; } int get_fail(int x){//和KMP一样,失配后找一个尽量最长的 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);//通过上一个回文串找这个回文串的匹配位置 if (!next[cur][c]){//如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串 int now=newnode(len[cur]+2);//新建节点 fail[now]=next[get_fail(fail[cur])][c];//和AC自动机一样建立fail指针,以便失配后跳转 next[cur][c]=now; num[now]=num[fail[now]]+1; } last=next[cur][c]; cnt[last]++; } void count(){//父亲累加儿子的cnt,因为如果fail[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; }
【回文自动机】bzoj3676 [Apio2014]回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。