AC自动机总结

hdu5995 H - Guessing the Dice Roll
一道经典题目(套路)，题意:有n个人都给出长度为m的序列，有一个骰子会一直摇，直到最后长度为m的序列出现了这n个人给出的序列，那个人就算赢了，求所有人赢的概率。
思路:首先用AC自动机存各个状态，用建立fail指针的方法来建立状态转移。然后用高斯消元建立方程组，方程解即是答案。
那么如何建立方程组呢。设结点为i,to=next[i][j],next[i][j]意为i状态摇到j后转移到的状态, 则A[to][i]+=1/6。别忘了A[i][i]=-1。
最后每一轮都会流进来一个1，它用A[0][tot]=-1来表示，最后算出的胜利结点的概率即是答案。

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define mem(a,x) memset(a,x,sizeof(a))
const int MAX=6;
const int maxn=100+5;

int n,L;
int node[maxn];
double A[maxn][maxn];
struct Trie
{
    int next[maxn][MAX],fail[maxn],end[maxn];
    int root,L;
    int newnode()
    {
        for(int i=0; i<MAX; i++)
            next[L][i]=-1;
        end[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(int str[],int len,int ID)
    {
        int now=root;
        for(int i=0; i<len; i++)
        {
            int id=str[i]-1;
            if(next[now][id]==-1)
                next[now][id]=newnode();
            now=next[now][id];
        }
        end[now]=ID;
        node[ID]=now;
    }
    void build()
    {
        queue<int>Q;
        fail[root]=root;
        for(int i=0; i<MAX; i++)
            if(next[root][i]==-1)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        while(!Q.empty())
        {
            int now=Q.front();
            Q.pop();
            for(int i=0; i<MAX; i++)
            {
                if(next[now][i]==-1)next[now][i]=next[fail[now]][i];
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }
} ac;
typedef double Matrix[maxn][maxn];
void Gauss(Matrix A,int n)
{
    for(int i=0; i<n; i++)
    {
        int r=i;
        for(int j=i+1; j<n; j++)
        {
            if(fabs(A[j][i])>fabs(A[r][i]))
                r=j;
        }
        if(r!=i)
        {
            for(int j=0; j<=n; j++)
                swap(A[i][j],A[r][j]);
        }
        for(int j=i+1; j<n; j++)
        {
            double f=A[j][i]/A[i][i];
            for(int k=i;k<=n;k++)
            {
                A[j][k]-=f*A[i][k];
            }
        }
    }

    for(int i=n-1;i>=0;i--)
    {
        for(int j=i+1;j<n;j++)
        {
            A[i][n]-=A[i][j]*A[j][n];
        }
        A[i][n]=A[i][n]/A[i][i];
    }
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ac.init();
        mem(A,0);
        int l;
        scanf("%d%d",&n,&l);
        int num[15];
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<l;j++)
            {
                scanf("%d",&num[j]);
            }
            ac.insert(num,l,i);
        }
        ac.build();
        int tot=ac.L;
        for(int i=0;i<tot;i++)
        {
            A[i][i]+=-1.0;
            if(ac.end[i])continue;
            for(int j=0;j<6;j++)
            {
                int to=ac.next[i][j];
                A[to][i]+=1.0/6.0;
            }
        }
        A[0][tot]=-1;
        Gauss(A,tot);

        for(int i=1;i<=n;i++)
        {
            int id=node[i];
            printf("%.6lf%c",A[id][tot],i==n?'\n':' ');
        }
    }
    return 0;
}