POJ 2778 DNA Sequence（AC自动机+矩阵加速）

DNA Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9899		Accepted: 3717

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

Source

POJ Monthly--2006.03.26,dodo

A自动机。

要求长度为n，不包含病毒串的个数。

首先利用AC自动机实现状态的转移。

AC自动机其实就和状态机类似的，可以产生L个状态。

然后根据状态间能不能转移，构造一个矩阵。

最后矩阵快速幂求解

//============================================================================

// Name        : HDU.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

using namespace std;

struct Matrix

{

    unsigned long long mat[][];

    int n;

    Matrix(){}

    Matrix(int _n)

    {

        n=_n;

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

            for(int j=;j<n;j++)

                mat[i][j] = ;

    }

    Matrix operator *(const Matrix &b)const

    {

        Matrix ret = Matrix(n);

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

            for(int j=;j<n;j++)

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

                    ret.mat[i][j]+=mat[i][k]*b.mat[k][j];

        return ret;

    }

};

unsigned long long pow_m(unsigned long long a,int n)

{

    unsigned long long ret=;

    unsigned long long tmp = a;

    while(n)

    {

        if(n&)ret*=tmp;

        tmp*=tmp;

        n>>=;

    }

    return ret;

}

Matrix pow_M(Matrix a,int n)

{

    Matrix ret = Matrix(a.n);

    for(int i=;i<a.n;i++)

        ret.mat[i][i] = ;

    Matrix tmp = a;

    while(n)

    {

        if(n&)ret=ret*tmp;

        tmp=tmp*tmp;

        n>>=;

    }

    return ret;

}

struct Trie

{

    int next[][],fail[];

    bool end[];

    int root,L;

    int newnode()

    {

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

            next[L][i] = -;

        end[L++] = false;

        return L-;

    }

    void init()

    {

        L = ;

        root = newnode();

    }

    void insert(char buf[])

    {

        int len = strlen(buf);

        int now = root;

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

        {

            if(next[now][buf[i]-'a'] == -)

                next[now][buf[i]-'a'] = newnode();

            now = next[now][buf[i]-'a'];

        }

        end[now] = true;

    }

    void build()

    {

        queue<int>Q;

        fail[root]=root;

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

            if(next[root][i] == -)

                next[root][i] = root;

            else

            {

                fail[next[root][i]] = root;

                Q.push(next[root][i]);

            }

        while(!Q.empty())

        {

            int now = Q.front();

            Q.pop();

            if(end[fail[now]])end[now]=true;

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

                if(next[now][i] == -)

                    next[now][i] = next[fail[now]][i];

                else

                {

                    fail[next[now][i]] = next[fail[now]][i];

                    Q.push(next[now][i]);

                }

        }

    }

    Matrix getMatrix()

    {

        Matrix ret = Matrix(L+);

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

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

                if(end[next[i][j]]==false)

                    ret.mat[i][next[i][j]] ++;

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

            ret.mat[i][L] = ;

        return ret;

    }

    void debug()

    {

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

        {

            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);

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

                printf("%2d",next[i][j]);

            printf("]\n");

        }

    }

};

char buf[];

Trie ac;

int main()

{

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

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

    int n,L;

    while(scanf("%d%d",&n,&L)==)

    {

        ac.init();

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

        {

            scanf("%s",buf);

            ac.insert(buf);

        }

        ac.build();

        Matrix a = ac.getMatrix();

        a = pow_M(a,L);

        unsigned long long res = ;

        for(int i = ;i < a.n;i++)

            res += a.mat[][i];

        res--;

        /*

         * f[n]=1 + 26^1 + 26^2 +...26^n

         * f[n]=26*f[n-1]+1

         * {f[n] 1} = {f[n-1] 1}[26 0;1 1]

         * 数是f[L]-1;

         * 此题的L<2^31.矩阵的幂不能是L+1次，否则就超时了

         */

        a = Matrix();

        a.mat[][]=;

        a.mat[][] = a.mat[][] = ;

        a=pow_M(a,L);

        unsigned long long ans=a.mat[][]+a.mat[][];

        ans--;

        ans-=res;

        cout<<ans<<endl;

    }

    return ;

}

巴特西

POJ 2778 DNA Sequence（AC自动机+矩阵加速）

最新文章

热门文章