poj2778之AC自动机+矩阵快速幂

DNA Sequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10171 Accepted: 3824

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首先要很蛋疼的说下我这个代码无论怎么样都只能跑到100+ms,跑不到排名上的几十ms甚至0ms,如果介意请无视，如果有大神能指出优化之处不胜感激

#include<iostream>   
#include<cstdio>   
#include<cstdlib>   
#include<cstring>   
#include<string>   
#include<queue>   
#include<algorithm>   
#include<map>   
#include<iomanip>   
#define INF 99999999   
using namespace std;  
  
const int MAX=100+10;//最大节点数    
const int mod=100000;  
__int64 array[MAX][MAX],sum[MAX][MAX];//进行矩阵乘法的初始矩阵和结果矩阵    
int n,m,size;//size表示节点个数   
char s[15];  
int Map[MAX];//映射A,C,G,T = 0,1,2,3   
  
struct TrieNode{  
    int id;//表示该节点的序号   
    bool mark;//标记是否是单词   
    TrieNode *fail,*next[4];//失败指针和下一个节点    
}*root,Node[MAX];  
  
TrieNode *New_TrieNode(){  
    memset(&Node[size],0,sizeof(TrieNode));  
    Node[size].id=size;  
    return &Node[size++];  
}  
  
void InsertNode(char *a){  
    TrieNode *p=root;  
    while(*a){  
        if(!p->next[Map[*a]])p->next[Map[*a]]=New_TrieNode();  
        p=p->next[Map[*a]];  
        ++a;  
    }  
    p->mark=true;  
}  
  
void Build_AC(){//建立AC自动机并且构造初始矩阵array    
    memset(array,0,sizeof array);  
    TrieNode *p=root,*next;  
    queue<TrieNode *>q;  
    q.push(root);  
    while(!q.empty()){  
        p=q.front();  
        q.pop();  
        for(int i=0;i<4;++i){  
            if(p->next[i]){  
                next=p->fail;  
                while(next && !next->next[i])next=next->fail;  
                p->next[i]->fail=next?next->next[i]:root;  
                if(p->next[i]->fail->mark)p->next[i]->mark=true;//防止ACG,AC这种一个病毒串的前缀是另一个病毒串的情况    
                q.push(p->next[i]);  
            }else p->next[i]=(p == root)?root:p->fail->next[i];//从这个点状态可以递推到失败指针节点的下一个节点状态    
            if(!p->next[i]->mark)++array[p->id][p->next[i]->id];//表示下一个状态不是病毒串,则可以到达    
        }  
    }  
}  
  
void MatrixMult(__int64 a[MAX][MAX],__int64 b[MAX][MAX]){  
    __int64 c[MAX][MAX]={0};  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j){  
            for(int k=0;k<size;++k){  
                c[i][j]+=a[i][k]*b[k][j];  
            }  
        }  
    }  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j)a[i][j]=c[i][j]%mod;  
    }  
}  
  
__int64 MatrixPow(int k){  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j)sum[i][j]=(i == j);//单位矩阵    
    }  
    while(k){  
        if(k&1)MatrixMult(sum,array);//sum=sum*array;   
        MatrixMult(array,array);//array=array*array;   
        k>>=1;  
    }  
    __int64 ans=0;  
    for(int i=0;i<size;++i)ans+=sum[0][i];//从0状态到达其他状态的所有总和   
    return ans%mod;   
}  
  
int main(){  
    Map['A']=0,Map['C']=1,Map['G']=2,Map['T']=3;  
    while(scanf("%d%d",&m,&n)!=EOF){  
        size=0;//节点个数初始化为0    
        root=New_TrieNode();//创建根节点   
        for(int i=0;i<m;++i){  
            scanf("%s",s);  
            InsertNode(s);   
        }  
        Build_AC();  
        printf("%I64d\n",MatrixPow(n));  
    }  
    return 0;  
}

补充：软件开发 , C++ ,