poj2778之AC自动机+矩阵快速幂 - c++编程基础

TOP

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

2014-11-23 19:33:20 来源: 作者: 【大中小】浏览:12次

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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#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;  
    queueq;  
    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>=1;  
    }  
    __int64 ans=0;  
    for(int i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2112 (最大流+二分)	下一篇：POJ 3984 迷宫问题 (DFS(深度优先..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: