首页 > 代码库 > 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(后缀自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。