首页 > 代码库 > 回文自动机(BZOJ2565)
回文自动机(BZOJ2565)
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int p,next[100001][27],cnt[100001],len[100001],fail[100001],last,a[100001],maxl[100001],maxr[100001]; char st[100001]; int newnode(int l){ p++; for (int i=1;i<=26;i++) next[p][i]=0; cnt[p]=0; len[p]=l; return(p); } void init(){ p=-1; newnode(0); newnode(-1); last=1; st[0]=-1; fail[0]=1; } int get_fail(int po,int x,int num){ while (a[po-len[x]-1]!=num) x=fail[x]; return(x); } void add(int po,int c){ int cur=get_fail(po,last,c); if (!next[cur][c]){ int now=newnode(len[cur]+2); fail[now]=next[get_fail(po,fail[cur],c)][c]; next[cur][c]=now; } last=next[cur][c]; cnt[last]++; } void count(){ for (int i=p;i>=0;i--) cnt[fail[i]]+=cnt[i]; } int main(){ scanf("%s",&st); int n=strlen(st); for (int i=1;i<=n;i++) a[i]=st[i-1]-‘a‘+1; init(); for (int i=1;i<=n;i++) add(i,a[i]),maxl[i]=len[last]; count(); for (int i=1;i<=n/2;i++){ int t=a[i];a[i]=a[n-i+1];a[n-i+1]=t; } init(); for (int i=1;i<=n;i++) add(i,a[i]),maxr[n-i+1]=len[last]; count(); int ans=0; for (int i=1;i<n;i++) ans=max(ans,maxl[i]+maxr[i+1]); printf("%d\n",ans); }
每个节点表示一个本质不同的回文串(最多n个)。
进行count()后,cnt中存每个本质不同的回文串的出现次数。
回文自动机(BZOJ2565)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。