poj 2778 DNA Sequence ac自动机+矩阵快速幂

题意:给定不超过10串，每串长度不超过10的灾难基因；问在之后给定的长度不超过2e9的基因长度中不包含灾难基因的基因有多少中?

DNA:只含'A','T','C','G'四种字符；

思路:这并不是很裸的ac自动机。。没有很明显的文本串匹配过程，但是我们能过通过对灾难基因建好Trie，在跑一下失配边时需要初始化状态转移矩阵了；

状态矩阵:每一次都可以往下一个位置走四个方向，但是要求不能走到单词节点。

(mat[i][j]) ^n: 表示走了n步，i 表示从那个节点开始走，j表示最终的字符(并不是特点的字符，可以表示多个合法的字符)；

即:第i个节点到第v个节点之间一步走有几种方法

　　　　　　　　$ ans = \sum \limits _{i=0}^{\rm size} mat\left [0 \right ]\left [ i \right ]$

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define MSi(a) memset(a,0x3f,sizeof(a))

#define inf 0x3f3f3f3f

#define lson l, m, rt << 1

#define rson m+1, r, rt << 1|1

#define sqr(a) (a)*(a)

typedef pair<int,int> PII;

#define A first

#define B second

#define MK make_pair

typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

int T,kase = ,i,j,k,n,m,top;

#define mod 100000

struct Matrix{

    int d[][];

    Matrix(int r = ){

        MS0(d);

        if(r){

            for(int i = ;i < top;i++)

                d[i][i] = ;

        }

    }

    Matrix operator*(const Matrix& a)const{

        Matrix ans;

        for(int i = ;i < top;i++)

        for(int j = ;j < top;j++){

            for(int k = ;k < top;k++)

                ans.d[i][j] = (ans.d[i][j]+1LL*d[i][k]*a.d[k][j]) % mod;

        }

        return ans;

    }

};

Matrix Pow(Matrix a,ll m)

{

    Matrix ans();

    while(m){

        if(m&) ans = ans*a;

        a = a*a;

        m >>= ;

    }

    return ans;

}

int h[];

const int sigma_size = ;

const int maxn = ;

struct Aho_Corasick{

    int ch[maxn][sigma_size];

    int val[maxn],f[maxn],last[maxn],cnt[maxn];

    int sz;

    map<string,int> ms;

    Aho_Corasick(){}

    void init(){sz = ;val[] = ; MS0(ch[]);MS0(cnt);ms.clear();}

    int idx(char c){return h[c];}

    void Insert(char *s,int v){

        int u = ,n = strlen(s);

        for(int i = ;i < n;i++){

            int c = idx(s[i]);

            if(!ch[u][c]){

                MS0(ch[sz]);

                val[sz] = ;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = v;

    }

    void getFail(){

        queue<int> q;

        f[] = ;

        //初始化队列

        for(int c = ;c < sigma_size;c++){

            int u = ch[][c];

            if(u) { f[u] = ; q.push(u); last[u] = ;}

        }

        while(!q.empty()){

            int r = q.front();q.pop();

            for(int c = ;c < sigma_size;c++){

                int u = ch[r][c];

                if(!u) {ch[r][c] = ch[f[r]][c]; continue;}//实现压缩

                q.push(u);

                int v = f[r];

                while(v && !ch[v][c]) v = f[v];

                f[u] = ch[v][c];

                last[u] = val[f[u]]?f[u]:last[f[u]];

            }

        }

    }

    //从文本串中找模板;

    Matrix Find(){

        Matrix ans;

        for(int i = ;i < sz;i++){

            if(val[i] || last[i]) continue;//合法即可

            for(int j = ;j < ;j++){ //每个节点都可以生成4个节点

                int v = ch[i][j];

                if(val[v] || last[v]) continue;

                ans.d[i][v]++; //也可以表示第i个节点到第v个节点之间一步走有几种方法;

            }

        }

        return ans;

    }

}ac;

char p[];

int main()

{

    ll n,m;

    //freopen("data.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    h['A'] = ;h['C'] = ;h['T'] = ;h['G'] = ;

    ac.init();

    read2(n,m);

    rep1(i,,n){

        scanf("%s",p);

        ac.Insert(p,i);

    }

    top = ac.sz;

    ac.getFail();

    Matrix ans = ac.Find();

    ans = Pow(ans,m);

    int cnt = ;

    rep0(i,,top)

        cnt += ans.d[][i];

    printf("%d\n",cnt%mod);

    return ;

}

秒客网

poj 2778 DNA Sequence ac自动机+矩阵快速幂

相关文章