首页 > 代码库 > HDU 4436 str2int(后缀自动机)

HDU 4436 str2int(后缀自动机)

 

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4436

 

【题目大意】 

  给出一些字符串,由0~9组成,求出所有不同子串的和。

 

【题解】

  将所有字符串添加拼接符10连接在一起建立自动机,
  从起点开始遍历所有节点,就能计算所有的子串和了。注意转移的时候只转移0到9节点。

 

【代码】

#include <cstdio>#include <cstring>#include <algorithm> #include <vector>using namespace std;const int N=200005,mod=2012;char s[N];int n;struct sam{	  int p,q,np,nq,cnt,last,a[N][11],l[N],f[N];	  sam(){cnt=0;last=++cnt;}	  void init(){	      cnt=0;last=++cnt;	      memset(a,0,sizeof(a));	      memset(l,0,sizeof(l));	      memset(f,0,sizeof(f));	      memset(b,0,sizeof(b));	      memset(x,0,sizeof(x));	      memset(sum,0,sizeof(sum));	      memset(t,0,sizeof(t));	  }	  void extend(int c){		    p=last;np=last=++cnt;l[np]=l[p]+1;		    while(!a[p][c]&&p)a[p][c]=np,p=f[p];		    if(!p)f[np]=1;		    else{			      q=a[p][c];			      if(l[p]+1==l[q])f[np]=q;			      else{				        nq=++cnt;l[nq]=l[p]+1;				        memcpy(a[nq],a[q],sizeof(a[q]));				        f[nq]=f[q]; f[np]=f[q]=nq;				        while(a[p][c]==q)a[p][c]=nq,p=f[p];			      }		    }	  }int b[N],x[N];	  void build(){	      int len=0;	      while(n--){	          scanf("%s",s);		        for(int i=0;s[i];i++)len++,extend(s[i]-‘0‘);		        extend(10),len++;		    }for(int i=1;i<=cnt;i++)b[l[i]]++;		    for(int i=1;i<=len;i++)b[i]+=b[i-1];		    for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i;	  }int sum[N],t[N];	  int solve(){	  	  int ans=0;	      sum[1]=0; t[1]=1;	      for(int i=1;i<=cnt;i++){	          int p=x[i];	          for(int j=0;j<10;j++){	              if(i==1&&j==0)continue;	              if(a[p][j]){	                  q=a[p][j];	                  t[q]=(t[p]+t[q])%mod;	                  sum[q]=(sum[q]+sum[p]*10+t[p]*j)%mod;	              }	          }ans=(ans+sum[p])%mod;	      }return ans;	  }}sam;int main(){    while(~scanf("%d",&n)){    	  sam.init();         sam.build();        printf("%d\n",sam.solve());    }return 0;}

  

HDU 4436 str2int(后缀自动机)