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 ;
}