POJ 2778 自动机_矩阵乘法

通过此题加上POJ 3691我对自动机有了更深的了解，不仅仅局限于字符串匹配，原来它是一种转移状态的机器。。。Orz。

POJ 2778
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分******************************************** 
struct Trie
{
    Trie *fail;
    Trie *next[4];
    bool isdanger;
    int num;
    Trie()
    {
        memset(next,NULL,sizeof(next));
        fail=NULL;
        isdanger=0;
    }
}*root,*T[10000];
int idx=0;
void NewTrie()
{
    T[idx]=new Trie();
    T[idx]->num=idx;
}
void Init()
{
    idx=0;        
    NewTrie();
    root=T[idx++];
}
int id(char s)
{
    switch(s)
    {
        case 'A': return 0;
        case 'T': return 1;
        case 'G': return 2;
        case 'C': return 3;
    }
}
void Insert(char *s)
{
    int j;
    Trie *r=root;
    for(j=0;j<strlen(s);j++)
    {
        int i=id(s[j]);
        if(r->next[i]==NULL)
        {
            NewTrie();
            r->next[i]=T[idx++];    
        }
        r=r->next[i];    
    }
    r->isdanger=1;
}
void BuildTrie()
{
    Trie *r=root,*p;
    queue<Trie *>q;
    root->fail=root;
    root->isdanger=0;
    q.push(root);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        p->isdanger=p->isdanger||p->fail->isdanger;
        for(int i=0;i<4;i++)
        {
            if(p->next[i]==NULL)//如果p->next[i]为空，则赋值为p的后缀的next[i]
            {
                if(p==root)
                    p->next[i]=root;
                else
                    p->next[i]=p->fail->next[i];
            }
            else //如果p->next[i]不为空，则构造后缀(失败)节点
            {
                if(p==root)
                    p->next[i]->fail=root;
                else
                    p->next[i]->fail=p->fail->next[i];
                q.push(p->next[i]);
            }            
        }
    }
}
//******************************************矩阵乘法部分********************************** 
struct MT
{
    __int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
    int i,j,k;
    MT res;
    memset(res.mt,0,sizeof(res.mt));
    for(i=0;i<idx;i++)
        for(j=0;j<idx;j++)
            if(a.mt[i][j])//矩阵乘法优化
            {
                for(k=0;k<idx;k++)
                {
                    res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
                    res.mt[i][k]%=MOD;
                }
            }
    return res;
}
MT Mi(MT a,int b)
{
    if(b==1)
        return a;
    MT t=Mi(a,b/2);
    MT tmp=Mult(t,t);
    if(b%2==1)
        return Mult(a,tmp);
    else return tmp;
}
void BuildStartMatrix(MT &start)
{
    int i,j;
    for(i=0;i<idx;i++)
    {
        if(T[i]->isdanger==0)
        {
            for(j=0;j<4;j++)
            {
                if(T[i]->next[j]->isdanger==0)
                    start.mt[i][T[i]->next[j]->num]++;
            }
        }
    }
} 
int n,m;
char ss[11];
int main()
{
    int i,j,k;
    scanf("%d%d",&m,&n);
    Init();
    while(m--)
    {
        scanf("%s",ss);
        Insert(ss);
    }
    BuildTrie();
    MT start;
    BuildStartMatrix(start); 
    MT res=Mi(start,n);
    int ans=0;
    for(i=0;i<idx;i++)
    {
        ans+=res.mt[0][i];
        ans%=MOD;
    }
    printf("%d\n",ans);
    return 0;
}

静态版本

静态版本
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分******************************************** 
struct Trie
{
    int fail;
    int next[4];
    bool isdanger;
    void init()
    {
        memset(next,-1,sizeof(next));
        fail=-1;
        isdanger=0;
    }
}T[10000];
int root;
int idx=0;
void Init()
{
    idx=0;        
    T[idx].init();
    root=idx;
    idx++;
}
int id(char s)
{
    switch(s)
    {
        case 'A': return 0;
        case 'T': return 1;
        case 'G': return 2;
        case 'C': return 3;
    }
}
void Insert(char *s)
{
    int j;
    int r=root;
    for(j=0;j<strlen(s);j++)
    {
        int i=id(s[j]);
        if(T[r].next[i]==-1)
        {
            T[idx].init();
            T[r].next[i]=idx;
            idx++;    
        }
        r=T[r].next[i];    
    }
    T[r].isdanger=1;
}
void BuildTrie()
{
    int r=root,p;
    queue<int >q;
    T[root].fail=root;
    T[root].isdanger=0;
    q.push(root);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        T[p].isdanger=T[p].isdanger||T[T[p].fail].isdanger;
        for(int i=0;i<4;i++)
        {
            if(T[p].next[i]==-1)
            {
                if(p==root)
                    T[p].next[i]=root;
                else
                    T[p].next[i]=T[T[p].fail].next[i];
            }
            else
            {
                if(p==root)
                    T[T[p].next[i]].fail=root;
                else
                    T[T[p].next[i]].fail=T[T[p].fail].next[i];
                q.push(T[p].next[i]);
            }            
        }
    }
}
//******************************************矩阵乘法部分********************************** 
struct MT
{
    __int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
    int i,j,k;
    MT res;
    memset(res.mt,0,sizeof(res.mt));
    for(i=0;i<idx;i++)
        for(j=0;j<idx;j++)
            if(a.mt[i][j])
            {
                for(k=0;k<idx;k++)
                {
                    res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
                    res.mt[i][k]%=MOD;
                }
            }
    return res;
}
MT Mi(MT a,int b)
{
    if(b==1)
        return a;
    MT t=Mi(a,b/2);
    MT res=Mult(t,t);
    if(b%2==1)
        return Mult(a,res);
    else return res;
}
void BuildStartMatrix(MT &start)
{
    int i,j;
    for(i=0;i<idx;i++)
    {
        if(T[i].isdanger==0)
        {
            for(j=0;j<4;j++)
            {
                if(T[T[i].next[j]].isdanger==0)
                    start.mt[i][T[i].next[j]]++;
            }
        }
    }
} 
int n,m;
char ss[11];
int main()
{
    int i,j,k;
    scanf("%d%d",&m,&n);
    Init();
    while(m--)
    {
        scanf("%s",ss);
        Insert(ss);
    }
    BuildTrie();
    MT start;
    BuildStartMatrix(start); 
    MT res=Mi(start,n);
    int ans=0;
    for(i=0;i<idx;i++)
    {
        ans+=res.mt[0][i];
        ans%=MOD;
    }
    printf("%d\n",ans);
    return 0;
}

发表于 2010-01-13 12:47 Headacher 阅读(1253) 评论(0) 编辑收藏引用所属分类: 数据结构和算法、ACM-ICPC

The One

搜索

积分与排名

积分 - 129214

排名 - 194

POJ 2778 自动机_矩阵乘法

公告

留言簿(8)

随笔分类

随笔档案

ACM Teammates

The One

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜