正文
POJ 3691 DNA Sequence （AC自动机 + 矩阵 有bug，待修改）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
DNA Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9889 | Accepted: 3712 |
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
Source
POJ Monthly--2006.03.26,dodo
不能AC，，可参考：http://blog.csdn.net/vasile010/article/details/4827921
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; const int N=;
const int mod=; struct Trie{
int ok;
int fail;
int next[];
void Init(){
ok=;
fail=-;
memset(next,-,sizeof(next));
}
}a[N]; char wrd[];
char str[N];
int n,m,cnt,q[N]; int find(char ch){
switch(ch){
case 'A':return ;
case 'C':return ;
case 'T':return ;
case 'G':return ;
}
return ;
} void InsertTrie(char *str){
int p=;
for(int i=;str[i]!='\0';i++){
int id=find(str[i]);
if(a[p].ok)
break;
if(a[p].next[id]==-){
a[p].next[id]=cnt++;
a[cnt-].Init();
}
p=a[p].next[id];
}
a[p].ok++;
} void AC_automation(){
int head=,tail=;
q[tail++]=;
int cur=,tmp;
while(head<tail){
cur=q[head++];
for(int i=;i<;i++){
tmp=a[cur].next[i];
if(tmp!=-){
if(cur==)
a[tmp].fail=;
else{
a[tmp].fail=a[a[cur].fail].next[i];
if(a[a[tmp].fail].ok)
a[tmp].ok++;
}
q[tail++]=a[cur].next[i];
}else{
if(cur==)
a[cur].next[i]=;
else
a[cur].next[i]=a[a[cur].fail].next[i];
}
}
}
} struct Matrix{
long long m[][];
}; Matrix init,unit; void Init(){
memset(init.m,,sizeof(init.m));
for(int i=;i<cnt;i++)
if(!a[i].ok)
for(int j=;j<;j++){
if(a[a[i].next[j]].ok==)
init.m[i][a[i].next[j]]++;
}
//if(a[*a[i].next[j]].ok==0)
//init.m[i][*a[i].next[j]]++;
for(int i=;i<cnt;i++)
for(int j=;j<cnt;j++)
unit.m[i][j]=(i==j)?:;
} Matrix Mul(Matrix a,Matrix b){
Matrix c;
for(int i=;i<cnt;i++)
for(int j=;j<cnt;j++){
c.m[i][j]=;
for(int k=;k<cnt;k++)
c.m[i][j]=(a.m[i][k]*b.m[k][j])%mod;
c.m[i][j]%=mod;
}
return c;
} Matrix Pow(Matrix a,Matrix b,int k){
while(k){
if(k&){
b=Mul(a,b);
}
a=Mul(a,a);
k>>=;
}
return b;
} int main(){ freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){
cnt=;
a[].Init();
for(int i=;i<n;i++){
scanf("%s",wrd);
InsertTrie(wrd);
}
AC_automation();
Init();
Matrix res=Pow(init,unit,m);
long long ans=;
for(int i=;i<cnt;i++)
if(a[i].ok==)
ans=(ans+res.m[][i])%mod;
cout<<ans<<endl;
}
return ;
}
