UVA 11468 Substring(AC自动机+概率DP)

UVA 11468 Substring(AC自动机+概率DP)

题意：

        给出一个单词字典，然后给出这个字典的所有字符以及其相应的出现概率，现在要随机生成一个长度为L的字符串s，问你s中没有字典中的任意一个单词的概率是多少？

分析：详见刘汝佳:训练指南P218

        构造完改造后的AC自动机后，每随机生成一个字母，相当于在AC自动机中随机走一步。所以有单词的节点标记为"禁止"。则本题就是求从节点0开始走L步，不进入任何禁止节点的概率。

        令d[i][j]表示当前在i节点，还有长为j的路要走且不经过单词节点的概率。初值为d[i][0]=1，其中i为非单词节点，否则d[i][0]=0。

        d[i][j] = sum( pro(x)*d[k][j-1] )。其中x表示从节点i往节点k走的那条边表示字符x，pro(x)是选择字符x的概率。 且k节点是非单词节点。所以利用记忆话搜索我们就可以计算出d[0][L]。

        代码中的match[i]表示节点i是否为单词节点 或 是否有单词正好是节点i的后缀。对于本题有了match数组就不必维护val和last数组了。

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxnode=500;
const int sigma_size=70;

int idx[256],n;


struct AC_Automata
{
    int ch[maxnode][sigma_size];
    int match[maxnode];
    int f[maxnode];
    int sz;
    void init()
    {
        sz=1;
        match[0]=0;
        memset(ch[0],0,sizeof(ch[0]));
    }
    void insert(char *s)
    {
        int n=strlen(s),u=0;
        for(int i=0;i<n;i++)
        {
            int id=idx[s[i]];
            if(ch[u][id]==0)
            {
                ch[u][id]=sz;
                memset(ch[sz],0,sizeof(ch[sz]));
                match[sz++]=0;
            }
            u=ch[u][id];
        }
        match[u]=u;
    }
    void getFail()
    {
        match[0]=f[0]=0;
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            int u=ch[0][i];
            if(u)
            {
                f[u]=0;
                q.push(u);
            }
        }
        while(!q.empty())
        {
            int r=q.front();q.pop();
            for(int i=0;i<n;i++)
            {
                int u=ch[r][i];
                if(!u)
                {
                    ch[r][i]=ch[f[r]][i];
                    continue;
                }
                q.push(u);
                int v=f[r];
                while(v && ch[v][i]==0) v=f[v];
                f[u]=ch[v][i];
                match[u] |= match[f[u]];
            }
        }
    }
};
double d[maxnode][105];
bool vis[maxnode][105];
char str[30][30];
AC_Automata ac;
double prob[256];
double get_pro(int i,int j)
{
    //if(!j) return 1.0;
    //if(vis[i][j]) return d[i][j];

    if(vis[i][j]) return d[i][j];
    if(j==0)
    {
        vis[i][j]=true;
        if(ac.match[i]) return d[i][j]=0.0;
        else return d[i][j]=1.0;
    }

    vis[i][j]=true;
    double &ans=d[i][j];
    ans=0.0;
    for(int k=0;k<n;k++)
    if(!ac.match[ac.ch[i][k]]) ans+= prob[k]*get_pro(ac.ch[i][k],j-1);
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        ac.init();
        int m;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s",str[i]);
        }
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            char s[30];
            scanf("%s %lf",s,&prob[i]);
            idx[s[0]]=i;
        }
        for(int i=0;i<m;i++)
            ac.insert(str[i]);
        ac.getFail();
        int L;
        scanf("%d",&L);
        memset(vis,0,sizeof(vis));
        printf("Case #%d: %.6lf\n",kase,get_pro(0,L));
    }
    return 0;
}