【POJ2778】AC自动机+矩阵乘法

DNA Sequence

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 14758 Accepted: 5716

Description

It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence，For example, if a animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments.

Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.

Input

First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.

Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.

Output

An integer, the number of DNA sequences, mod 100000.

Sample Input
4 3
AT
AC
AG
AA
Sample Output
36



【分析】
　　之前做过的题。  建立一个AC自动机，然后把每个字符串的最后一位所在的节点标黑。（就是把mark变为1） 然后用AC自动机建立矩阵array[i][j]表示从i走到j的方案数，然后利用矩阵乘法的性质，用快速幂求出矩阵的M次幂即可。


代码依然丑：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 1010
  9 #define LL long long
 10 #define Mod 100000
 11 
 12 struct node
 13 {
 14     int x,fail;
 15     int son[6];
 16     bool mark;
 17 }t[Maxn];int tot=0;
 18 
 19 struct Matrix
 20 {
 21     LL a[110][110];
 22 }ay,ut;
 23 
 24 void upd(int x)
 25 {
 26     t[x].mark=0;
 27     memset(t[x].son,0,sizeof(t[x].son));
 28 }
 29 
 30 Matrix h;
 31 void clear(int id)
 32 {
 33     for(int i=0;i<=tot;i++)
 34      for(int j=0;j<=tot;j++)
 35       if(id==1) ay.a[i][j]=0;
 36       else h.a[i][j]=0;
 37 }
 38 
 39 int m,n;
 40 char s[Maxn];
 41 
 42 void read_trie()
 43 {
 44     scanf("%s",s+1);
 45     int len=strlen(s+1);
 46     int now=0;
 47     for(int i=1;i<=len;i++)
 48     {
 49         int ind;
 50         if(s[i]=='A') ind=1;
 51         else if(s[i]=='T') ind=2;
 52         else if(s[i]=='C') ind=3;
 53         else ind=4;
 54         if(!t[now].son[ind])
 55         {
 56             t[now].son[ind]=++tot,upd(tot);
 57         }
 58         now=t[now].son[ind];
 59         if(i==len) t[now].mark=1;
 60     }
 61 }
 62 
 63 queue<int > q;
 64 void build_AC()
 65 {
 66     while(!q.empty()) q.pop();
 67     q.push(0);
 68     while(!q.empty())
 69     {
 70         int now=q.front();q.pop();
 71         int f=t[now].fail;
 72         for(int i=1;i<=4;i++)
 73         {
 74             if(t[now].son[i])
 75             {
 76                 q.push(t[now].son[i]);
 77                 t[t[now].son[i]].fail=now?t[f].son[i]:0;
 78                 if(t[t[t[now].son[i]].fail].mark) t[t[now].son[i]].mark=1;
 79             }
 80             else t[now].son[i]=t[f].son[i];
 81             if(t[t[now].son[i]].mark!=1) ay.a[now][t[now].son[i]]++;
 82         }
 83     }
 84 }
 85 
 86 Matrix mul(Matrix a,Matrix b)
 87 {
 88     clear(2);
 89     for(int i=0;i<=tot;i++)
 90      for(int j=0;j<=tot;j++)
 91       for(int k=0;k<=tot;k++)
 92       {
 93         h.a[i][j]=(h.a[i][j]+a.a[i][k]*b.a[k][j])%Mod;
 94           
 95       }
 96     return h;
 97 }
 98 
 99 void qpow(int k)
100 {
101     while(k)
102     {
103         if(k&1) ut=mul(ut,ay);
104         ay=mul(ay,ay);
105         k>>=1;
106     }
107 }
108 
109 void init()
110 {
111     scanf("%d%d",&m,&n);
112     tot=0;upd(0);
113     for(int i=1;i<=m;i++)
114     {
115         read_trie();
116     }
117     clear(1);
118     build_AC();
119     for(int i=0;i<=tot;i++)
120      for(int j=0;j<=tot;j++)
121         ut.a[i][j]=i==j?1:0;
122      
123     qpow(n);
124     LL ans=0;
125     for(int i=0;i<=tot;i++) ans=(ans+ut.a[0][i])%Mod;
126     printf("%I64d
",ans);
127 }
128 
129 int main()
130 {
131     init();
132     return 0;
133 }

[POJ2778]

以前的code：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int Maxn=150;
  9 const int Mod=(int)1e5;
 10 char s[Maxn];
 11 int q[Maxn];
 12 long long ay[Maxn][Maxn],sum[Maxn][Maxn];
 13 int n,m,tot,len;
 14 
 15 struct node
 16 {
 17     int son[6],cnt,fail,mark;
 18 }t[Maxn];
 19 
 20 void floy()
 21 {
 22     tot=0;
 23     for(int i=1;i<=Maxn;i++)
 24     {
 25         t[i].cnt=0;t[i].mark=0;
 26         for(int j=1;j<=5;j++) t[i].son[j]=0;
 27     }
 28     memset(q,0,sizeof(q));
 29 }
 30 
 31 void read_trie()
 32 {
 33     tot=0;
 34     int i,j;
 35     scanf("%d%d",&m,&n);
 36     for(i=1;i<=m;i++)
 37     {
 38         int x,ind;
 39         scanf("%s",s+1);
 40         len=strlen(s+1);
 41         x=0;
 42         for(j=1;j<=len;j++)
 43         {
 44             if(s[j]=='A') ind=1;
 45             else if(s[j]=='C') ind=2;
 46             else if(s[j]=='T') ind=3;
 47             else if(s[j]=='G') ind=4;
 48             if(!t[x].son[ind]) t[x].son[ind]=++tot;
 49             x=t[x].son[ind];
 50             t[x].cnt++;
 51             if(j==len) t[x].mark=1;
 52         }
 53     }
 54 }
 55 
 56 void build_AC()
 57 {
 58     int i,j,x,y;
 59     q[++q[0]]=0;
 60     //for(i=1;i<=4;i++)
 61       //if(t[0].son[i]) q[++q[0]]=t[0].son[i];
 62     for(i=1;i<=q[0];i++)
 63     {
 64         x=q[i];
 65         y=t[x].fail;
 66         for(j=1;j<=4;j++)
 67         {
 68             if(t[x].son[j])
 69             {
 70                 //t[t[x].son[j]].fail=t[y].son[j];
 71                 q[++q[0]]=t[x].son[j];
 72                  t[t[x].son[j]].fail=x?t[y].son[j]:x;  
 73                 if(t[t[t[x].son[j]].fail].mark) t[t[x].son[j]].mark=1;
 74             }
 75             else t[x].son[j]=t[y].son[j];
 76             if(!t[t[x].son[j]].mark) ay[x][t[x].son[j]]++;
 77         }
 78     }
 79 }
 80 
 81 void MatrixMult(long long a[Maxn][Maxn],long long b[Maxn][Maxn])
 82 {
 83     int i,j,k;
 84     long long c[Maxn][Maxn];
 85     memset(c,0,sizeof(c));
 86     for(i=0;i<=tot;i++)
 87      for(j=0;j<=tot;j++)
 88       for(k=0;k<=tot;k++)
 89        c[i][j]+=a[i][k]*b[k][j];
 90     for(i=0;i<=tot;i++)
 91      for(j=0;j<=tot;j++)
 92       a[i][j]=c[i][j]%Mod;
 93 }
 94 
 95 long long MatrixPow(int k)
 96 {
 97     int i,j;
 98     for(i=0;i<=tot;i++)
 99      for(j=0;j<=tot;j++)
100        sum[i][j]=(i==j);
101     while(k)
102     {
103         if(k&1) MatrixMult(sum,ay);
104         MatrixMult(ay,ay);
105         k>>=1;
106     }
107     long long ans=0;
108     for(i=0;i<=tot;i++) ans+=sum[0][i];
109     return ans%Mod;
110 }
111 
112 int main()
113 {
114     floy();
115     read_trie();
116     build_AC();
117     printf("%I64d
",MatrixPow(n));
118     return 0;
119 }

[POJ2778_2]

2016-06-23 16:22:32

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 14758	Accepted: 5716