首页 > 代码库 > 回文自动机(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)