Free tutorials to bookmark

POJ 2778 DNA Sequence

Problem :Models that contain only (a, g, c, t) (M <= 10, Len <= 10), and ask all the string with (A, G, C, T) with all length n contains (A, G, C, T) How many of them contain pattern string. (n <= 2000000000)
Solution :First establish an AC automatic machine for all modes. Then DP [i] [j] indicates that the length of the length of the AC automatic machine J is to meet the number of strings such as the node j of the AC automatic machine. Operation.

#include <iostream>
#include <string>
#include <queue>

using namespace std;

const int N = 208;
const int mo = 100000;

int id[128];

struct Matrix
{
    int n;
    int a[N][N];
    Matrix(int n_, int p)
    {
        n = n_;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
            {
                a[i][j] = 0;
                if (i == j) a[i][j] = p;
            }
    }
    friend Matrix operator *(Matrix A, Matrix B)
    {
        Matrix C(A.n, 0);
        for (int i = 0; i < A.n; ++i)
            for (int j = 0; j < A.n; ++j)
                for (int k = 0; k < A.n; k++)
                    C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j] % mo) % mo; 
        return C;
    }
    void print()
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j) cout << a[i][j] << " ";
            cout << endl;
        }
    }
};

struct AC_Automan
{
    int next[N][4];
    int fail[N];
    int cnt[N];
    int root, tot;
    
    int newnode()
    {
        for (int i = 0; i <= 3; ++i) next[tot][i] = -1;
        fail[tot] = cnt[tot] = -1;
        return tot++;
    }
    void clear()
    {
        tot = 0;
        root = newnode();
    }
    void insert(const string &s)
    {
        int p = root;
        for (int i = 0, len = s.length(); i < len; ++i)
        {
            if (next[p][id[s[i]]] == -1) next[p][id[s[i]]] = newnode();
            p = next[p][id[s[i]]];
        }
        cnt[p] = 1;
    }
    void build()
    {
        queue <int> Q;
        Q.push(root);
        while (!Q.empty())
        {
            int p = Q.front(); Q.pop();
            for (int i = 0; i < 4; ++i)
            {
                if (~next[p][i])
                {
                    if (p == root) fail[next[p][i]] = root; 
                    else fail[next[p][i]] = next[fail[p]][i];
                    Q.push(next[p][i]);
                }       
                else
                {
                    if (p == root) next[p][i] = root;
                    else next[p][i] = next[fail[p]][i];
                }
            }
        }
    }
    Matrix power(Matrix A, int y)
    {
        Matrix B(tot, 1);
        while (y)
        {
            if (y & 1) B = B * A;
            A = A * A;
            y >>= 1;
        }
        return B;
    }

    void solve(int num)
    {
        Matrix A(tot, 0);
        for (int i = 0; i <= tot; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                int flag = 1;
                for (int temp = next[i][j]; temp != root; temp = fail[temp])
                {
                    if (~cnt[temp]) flag = 0;
                }
                A.a[i][next[i][j]] += flag;
            }
        }
        A = power(A, num);
        int ans = 0;
        for (int i = 0; i < tot; ++i) ans = (ans + A.a[0][i]) % mo;
        cout << ans << endl;
    }
}ac;



int main()
{
    cin.sync_with_stdio(0);
    id['A'] = 0; id['G'] = 1; id['C'] = 2; id['T'] = 3;
    int m, n;
    while (cin >> m >> n)
    {
        ac.clear();
        for (int i = 1; i <= m; ++i)
        {
            string s; cin >> s;
            ac.insert(s);
        }
        ac.build();
        ac.solve(n);
    }
}