poj 2778 DNA Sequence

ac自動機處理字符串，dp計算答案，用矩陣來加速[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <queue>  
using namespace std; 
const long long mod=100000; 
struct 
{ 
    int next[30],tmp,fail,lon; 
}trie[111]; 
int lon; 
int m,n; 
struct matrix 
{ 
    long long data[111][111]; 
    int size; 
    matrix(int tmp,int lon) 
    { 
        size=lon; 
        for(int i=0;i<=size;i++) 
        for(int j=0;j<=size;j++) 
        data[i][j]=tmp; 
    } 
    matrix operator * (const matrix &xx) const 
    { 
        matrix ans(0,size); 
        for(int p=0;p<=size;p++) 
        for(int q=0;q<=size;q++) 
        for(int i=0;i<=size;i++) 
        { 
            ans.data[p][q]+=data[p][i]*xx.data[i][q]; 
            ans.data[p][q]%=mod; 
        } 
        return(ans); 
    } 
}; 
void trieini() 
{ 
    memset(trie,0,sizeof(trie)); 
    lon=0; 
} 
void insert(char s[]) 
{ 
    int t=0; 
    int n=strlen(s+1); 
    for(int i=1;i<=n;i++) 
    { 
        if(trie[t].next[s[i]-'A']==0) 
        { 
            trie[t].next[s[i]-'A']=++lon; 
            trie[lon].lon=i; 
        } 
        t=trie[t].next[s[i]-'A']; 
        if(i==n) 
        trie[t].tmp++; 
    } 
} 
 
void getfail() 
{ 
    int root=0; 
    queue <int> q; 
    q.push(root); 
    trie[root].fail=root; 
    while(!q.empty()) 
    { 
        int t=q.front(); 
        q.pop(); 
        for(int i=0;i<26;i++) 
        { 
            if(trie[t].next[i]) 
            { 
                if(t==root) 
                { 
                    int u=trie[t].next[i]; 
                    trie[u].fail=root; 
                    q.push(u); 
                    continue; 
                } 
                int u=trie[t].next[i]; 
                int tmp=trie[t].fail; 
                while(tmp!=root&&trie[tmp].next[i]==0) 
                tmp=trie[tmp].fail; 
                if(trie[tmp].next[i]) 
                trie[u].fail=trie[tmp].next[i]; 
                else 
                trie[u].fail=root; 
                q.push(u); 
            } 
        } 
    } 
    for(int i=1;i<=lon;i++) 
    { 
        int t=i; 
        while(t!=root) 
        { 
            int u=trie[t].fail; 
            trie[t].tmp+=trie[u].tmp; 
            t=u; 
        } 
    } 
} 
 
void find(matrix &a) 
{ 
    int root=0; 
    for(int k=0;k<=lon;k++) 
    { 
        if(trie[k].tmp) continue; 
        for(int i=0;i<26;i++) 
        { 
            if(i+'A'!='A') 
            if(i+'A'!='C') 
            if(i+'A'!='T') 
            if(i+'A'!='G') 
            continue; 
            int t=k; 
            while(t!=root&&trie[t].next[i]==0) 
            t=trie[t].fail; 
 
            if(trie[t].next[i]) 
            { 
                int u=trie[t].next[i]; 
                if(!trie[u].tmp) 
                a.data[k][u]++; 
            } 
            else 
            a.data[k][0]++; 
        } 
    } 
} 
 
int main() 
{ 
    while(scanf("%d %d",&m,&n)!=EOF) 
    { 
        trieini(); 
        char s[15]; 
        for(int i=1;i<=m;i++) 
        { 
            scanf("%s",s+1); 
            insert(s); 
        } 
        getfail(); 
        matrix a(0,lon); 
        find(a); 
        matrix ans(a); 
        n--; 
        while(n) 
        { 
            if(n&1) 
            ans=ans*a; 
            a=a*a; 
            n/=2; 
        } 
        int answer=0; 
        for(int i=0;i<=lon;i++) 
        { 
            answer+=ans.data[0][i]; 
            answer%=mod; 
        } 
        cout<<answer<<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const long long mod=100000;
struct
{
    int next[30],tmp,fail,lon;
}trie[111];
int lon;
int m,n;
struct matrix
{
    long long data[111][111];
    int size;
    matrix(int tmp,int lon)
    {
        size=lon;
        for(int i=0;i<=size;i++)
        for(int j=0;j<=size;j++)
        data[i][j]=tmp;
    }
    matrix operator * (const matrix &xx) const
    {
        matrix ans(0,size);
        for(int p=0;p<=size;p++)
        for(int q=0;q<=size;q++)
        for(int i=0;i<=size;i++)
        {
            ans.data[p][q]+=data[p][i]*xx.data[i][q];
            ans.data[p][q]%=mod;
        }
        return(ans);
    }
};
void trieini()
{
    memset(trie,0,sizeof(trie));
    lon=0;
}
void insert(char s[])
{
    int t=0;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        if(trie[t].next[s[i]-'A']==0)
        {
            trie[t].next[s[i]-'A']=++lon;
            trie[lon].lon=i;
        }
        t=trie[t].next[s[i]-'A'];
        if(i==n)
        trie[t].tmp++;
    }
}

void getfail()
{
    int root=0;
    queue <int> q;
    q.push(root);
    trie[root].fail=root;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(trie[t].next[i])
            {
                if(t==root)
                {
                    int u=trie[t].next[i];
                    trie[u].fail=root;
                    q.push(u);
                    continue;
                }
                int u=trie[t].next[i];
                int tmp=trie[t].fail;
                while(tmp!=root&&trie[tmp].next[i]==0)
                tmp=trie[tmp].fail;
                if(trie[tmp].next[i])
                trie[u].fail=trie[tmp].next[i];
                else
                trie[u].fail=root;
                q.push(u);
            }
        }
    }
    for(int i=1;i<=lon;i++)
    {
        int t=i;
        while(t!=root)
        {
            int u=trie[t].fail;
            trie[t].tmp+=trie[u].tmp;
            t=u;
        }
    }
}

void find(matrix &a)
{
    int root=0;
    for(int k=0;k<=lon;k++)
    {
        if(trie[k].tmp) continue;
        for(int i=0;i<26;i++)
        {
            if(i+'A'!='A')
            if(i+'A'!='C')
            if(i+'A'!='T')
            if(i+'A'!='G')
            continue;
            int t=k;
            while(t!=root&&trie[t].next[i]==0)
            t=trie[t].fail;

            if(trie[t].next[i])
            {
                int u=trie[t].next[i];
                if(!trie[u].tmp)
                a.data[k][u]++;
            }
            else
            a.data[k][0]++;
        }
    }
}

int main()
{
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        trieini();
        char s[15];
        for(int i=1;i<=m;i++)
        {
            scanf("%s",s+1);
            insert(s);
        }
        getfail();
        matrix a(0,lon);
        find(a);
        matrix ans(a);
        n--;
        while(n)
        {
            if(n&1)
            ans=ans*a;
            a=a*a;
            n/=2;
        }
        int answer=0;
        for(int i=0;i<=lon;i++)
        {
            answer+=ans.data[0][i];
            answer%=mod;
        }
        cout<<answer<<endl;
    }
    return 0;
}