POJ 2778 DNA Sequence

做的第一道AC自动机非模板题，感觉真的是神了。
一些AC自动机的性质自己完全不知道……

废话不多说，直接上题解。

题意：
给你( n )种病毒，要你求出长度为 ( m ) 的不含这 ( n ) 中病毒的数量。

思路：
这道题可以转化成图论解决，当然只能是思路而已
对于AC自动机上的每一个结点，他都可以看成是一个字符串的一部分前缀，也可以认为是一个字符串的一部分后缀。
作为一部分后缀，如果我们在一直不含病毒串的同时，长度达到了要求，我们就可以将其认为是一种可行方案。

解题关键 : 离散数学上的矩阵阶乘定理

构建一个矩阵，矩阵值 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到 ( j ) 的边数。对其求 k 次幂，所得新矩阵为 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到 ( j ) 长度为 ( k ) 的路径数量。

应用到这题来，其实我们对于AC自动机上的每一个结点，我们只要求出它的邻接矩阵，再通过矩阵快速幂，累加和，就是我们要的答案。

下面是求邻接矩阵的方法与说明

作为一部分前缀，如果这个结点它选择走向了另一个结点从而形成了我们的病毒串，我们认为这是不可行的。
这是很显然的，比如说有病毒串 ATC ，而我 当前结点及其它的所有前结点构成的字符串为 *****AT，如果这时候我们走向了 T 的孩子 C结点 ，这时候就构成了病毒串，我这里暂时称它为病毒结点。

另一个不允许我们跑动的状态是跑 fail 指针的时候。当我们已知我们的fail指针是指向的病毒结点的时候，我们自然不能通过这个fail指针跑向病毒结点。并且我们的当前结点也成为了病毒结点。因为他们的后缀相同。
举个例子就比如 R -> ATC ，T指向了 R -> T ，其中 T 为病毒结点，那么 R -> AT 中的 T 也成为了病毒结点。

初学者 当然包括我啦 有个很自然的困惑就是这样的情况 R -> ATCT , R -> T 病毒结点的时候，R -> ATCT 的第一个 T 能不能有效的被 “感染” 为病毒结点。
答案当然是显然的，因为我们的遍历过程是宽度优先。如果是深度优先，恐怕不行。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef long long ll;
const int max_n = 120;
const int max_c = 4;
const int mod = 1e5;
char buf[max_n];

int getChar(char& ch)
{
    if (ch == 'A')
        return 0;
    else if (ch == 'C')
        return 1;
    else if (ch == 'G')
        return 2;
    return 3;
}

struct Matrix {
    int mat[max_n][max_n], n;
    Matrix(int _n = 1)
    {
        n = _n;
        memset(mat, 0, sizeof mat);
    }
    Matrix operator*(const Matrix& a) const
    {
        Matrix tmp(n);
        for (int i = 1; i < n; ++i)
            for (int j = 1; j < n; ++j)
                if (mat[i][j])
                    for (int k = 1; k < n; ++k)
                        tmp.mat[i][k] = (tmp.mat[i][k] + 1LL * mat[i][j] * a.mat[j][k] % mod) % mod;
        return tmp;
    }
};

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    inline void insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = getChar(str[i]);
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            if (end[fail[now]])
                end[now] = 1;
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    Matrix getMatrix()
    {
        Matrix a(size);
        for (int i = 1; i < size; i++)
            for (int j = 0; j < 4; j++)
                if (!end[next[i][j]])
                    a.mat[i][next[i][j]]++;
        return a;
    }
} aho;

Matrix Pow(Matrix a, ll m)
{
    Matrix ans(a.n);
    for (int i = 1; i < a.n; i++)
        ans.mat[i][i] = 1;
    while (m) {
        if (m & 1)
            ans = ans * a;
        a = a * a;
        m >>= 1;
    }
    return ans;
}

int main()
{
    int n;
    ll m;
    while (scanf("%d %lld", &n, &m) != EOF) {
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        Matrix a = aho.getMatrix();
        a = Pow(a, m);
        int res = 0;
        for (int i = 1; i < a.n; i++)
            res = (res + a.mat[1][i]) % mod;
        printf("%d\n", res);
    }
    return 0;
}