首页 > 代码库 > 【hdu4436/LA6387-str2int】sam处理不同子串
【hdu4436/LA6387-str2int】sam处理不同子串
题意：给出n个数字，数字很长，用字符串读入，长度总和为10^5。求这n个字符串的所有子串（不重复）的和取模2012 。
例如字符串101，和就是1+10+101=112。
题解：
就是求不同的子串连成一个数。
sam的拓扑序真的很有用！按拓扑序可以保证能转移到当前x的节点都在之前被更新了。
每个节点x维护cnt表示root到x的方案数，sum表示以x为结尾的子串和。
找拓扑序有两种方法：1.拓扑排序一样bfs(O(n)) 2.按照step[x]排序（若x有个孩子是y，step[x]<=step[y](O(nlogn))
按照拓扑序for一遍，对于x，它的孩子y,cnt[y]+=cnt[x],sum[y]+=sum[x]*10+cnt[x]*(y所代表的数字)。
不能有前缀0----->根节点不走0孩子。
节点数开了10^6才AC。tell me why?!
打了两种求拓扑序的方法。
贴一下代码。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<queue> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 10 const int N=10*100010,Mod=2012; 11 char s[N]; 12 int n,sl,cl,ans,tot,last; 13 int son[N][30],pre[N],step[N],sum[N],in[N],cnt[N],c[N]; 14 bool vis[N]; 15 queue<int> Q; 16 17 int add_node(int x) 18 { 19 step[++tot]=x; 20 return tot; 21 } 22 23 void extend(int ch) 24 { 25 int p=last,np=add_node(step[last]+1); 26 while(p && !son[p][ch]) son[p][ch]=np,in[np]++,p=pre[p]; 27 if(!p) pre[np]=1; 28 else 29 { 30 int q=son[p][ch]; 31 if(step[q]==step[p]+1) pre[np]=q; 32 else 33 { 34 int nq=add_node(step[p]+1); 35 memcpy(son[nq],son[q],sizeof(son[q])); 36 for(int i=0;i<=9;i++) 37 if(son[q][i]) in[son[q][i]]++; 38 pre[nq]=pre[q]; 39 pre[np]=pre[q]=nq; 40 while(son[p][ch]==q) in[q]--,in[nq]++,son[p][ch]=nq,p=pre[p]; 41 } 42 } 43 last=np; 44 } 45 46 void find_tp_1() 47 { 48 for(int i=2;i<=tot;i++) 49 { 50 if(in[i]==0) 51 { 52 for(int j=0;j<=9;j++) 53 { 54 int y=son[i][j]; 55 if(!y) continue; 56 in[y]--; 57 } 58 } 59 } 60 while(!Q.empty()) Q.pop(); 61 Q.push(1);vis[1]=1;cl=0; 62 while(!Q.empty()) 63 { 64 int x=Q.front();vis[x]=0;c[++cl]=x;Q.pop(); 65 for(int i=0;i<=9;i++) 66 { 67 int y=son[x][i]; 68 if(!y) continue; 69 in[y]--; 70 if(!in[y] && !vis[y]) vis[y]=1,Q.push(y); 71 } 72 } 73 } 74 75 bool cmp(int x,int y){return step[x]<step[y];} 76 void find_tp_2() 77 { 78 cl=0; 79 for(int i=1;i<=tot;i++) 80 { 81 if(in[i] || i==1) c[++cl]=i; 82 } 83 sort(c+1,c+1+cl,cmp); 84 } 85 86 void solve() 87 { 88 cnt[1]=1; 89 for(int i=1;i<=cl;i++) 90 { 91 int x=c[i]; 92 for(int j=0;j<=9;j++) 93 { 94 int y=son[x][j]; 95 if(!y || (x==1 && j==0)) continue; 96 cnt[y]=(cnt[y]+cnt[x])%Mod; 97 sum[y]=(sum[y]+(sum[x]*10)%Mod+(j*cnt[x])%Mod)%Mod; 98 } 99 }100 }101 102 int main()103 {104 freopen("a.in","r",stdin);105 // freopen("me.out","w",stdout);106 while(scanf("%d",&n)!=EOF)107 {108 memset(son,0,sizeof(son));109 memset(step,0,sizeof(step));110 memset(pre,0,sizeof(pre));111 memset(in,0,sizeof(in));112 memset(cnt,0,sizeof(cnt));113 memset(sum,0,sizeof(sum));114 tot=0;add_node(0);last=1;115 for(int i=1;i<=n;i++) 116 {117 scanf("%s",s+1);118 sl=strlen(s+1);119 last=1;120 for(int j=1;j<=sl;j++) extend(s[j]-‘0‘);121 }122 find_tp_1();//找拓扑序方法一 ： bfs=拓扑排序123 // find_tp_2();//方法二：直接对step[x]进行排序124 solve();125 ans=0;126 for(int i=1;i<=tot;i++) ans=(ans+sum[i])%Mod;127 printf("%d\n",ans);128 // cout<<"Time Used : "<<(double)clock()/CLOCKS_PER_SEC<<" s."<<endl;129 }130 return 0;131 }
【hdu4436/LA6387-str2int】sam处理不同子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。