data矩阵poj 2778 DNA Sequence

最近研究data矩阵，稍微总结一下，以后继续补充：

ac自动机处理字符串，dp计算谜底，用矩阵来减速

每日一道理
巴尔扎克说过“不幸，是天才的进升阶梯，信徒的洗礼之水，弱者的无底深渊”。风雨过后，眼前会是鸥翔鱼游的天水一色；走出荆棘，前面就是铺满鲜花的康庄大道；登上山顶，脚下便是积翠如云的空蒙山色。在这个世界上，一星陨落，黯淡不了星空灿烂，一花凋零，荒芜不了整个春天。人生要尽全力度过每一关，不管遇到什么困难不可轻言放弃。

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

}

文章结束给大家分享下程序员的一些笑话语录： IBM和波音777
　　波音777是有史以来第一架完全在电脑虚拟现实中设计制造的飞机，所用的设备完全由IBM公司所提供。试飞前，波音公司的总裁非常热情的邀请IBM的技术主管去参加试飞，可那位主管却说道:“啊，非常荣幸，可惜那天是我妻子的生日，So..”..
　　波音公司的总载一听就生气了:“胆小鬼，我还没告诉你试飞的日期呢!”

---------------------------------
原创文章 By
data和矩阵
---------------------------------

巴特西

data矩阵poj 2778 DNA Sequence

最新文章

热门文章