回文自动机（BZOJ2565）-白红宇

回文自动机（BZOJ2565）

阅读量：5980 次

发布时间：2019-06-20

本文共 3397 字，大约阅读时间需要 11 分钟。

#include 
     
      #include 
      
       #include 
       
        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个）。

进行count()后，cnt中存每个本质不同的回文串的出现次数。

------------------------------------------------------------------------

CODECHEF APRIL LUNCHTIME 2015 PALPROB

在fail树上转移palindromness

#include 
     
      #include 
      
       #include 
       
        #include 
        #define LL long longusing namespace std;  map 
         
           mp,mpb;  int p,tr[110001][27],cnt[110001],len[110001],fail[110001],last,a[110001],maxl[110001],maxr[110001];  int ans[110001],nd[110001],nxt[110001],des[110001],T,scnt;  char st[110001];  void addedge(int x,int y){      nxt[++scnt]=nd[x];des[scnt]=y;nd[x]=scnt;  }  int newnode(int l){    p++;    for (int i=1;i<=26;i++) tr[p][i]=0;    cnt[p]=0;ans[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 (tr[cur][c]==0){      int now=newnode(len[cur]+2);      fail[now]=tr[get_fail(po,fail[cur],c)][c];      tr[cur][c]=now;    }    last=tr[cur][c];    cnt[last]++;  }  void count(){    for (int i=p;i>=0;i--) cnt[fail[i]]+=cnt[i];  }      void dfs(int po){      if (len[po]>=0){        int t;      if (len[po]<=1) t=-1;else t=len[po]/2;      int p=mp[t];      if (mpb[t])        ans[po]=ans[p]+1;else        ans[po]=1;    }        mpb[len[po]]=1;mp[len[po]]=po;    for (int p=nd[po];p!=-1;p=nxt[p])       dfs(des[p]);     mpb[len[po]]=0;  }       int main(){     freopen("a.in","r",stdin);      scanf("%d",&T);    while (T--){      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]);      count();                for (int i=0;i<=p;i++) nd[i]=-1;scnt=0;      for (int i=0;i<=p;i++) if (i!=1) addedge(fail[i],i);            mp.clear();mpb.clear();      dfs(1);            LL ret=0;      for (int i=2;i<=p;i++) ret+=(LL)ans[i]*cnt[i];      printf("%lld\n",ret);    }      }