【题意】

【解题方法】

详细可见白书P 218

构造完改造后的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 代码】

//
//Created by just_sort 2016/8/20
//All Rights Reserved
//

#include <map>
#include <queue>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 500;
const int maxs = 100;
int n,m,id[maxn];

struct acautomata{
    int nxt[maxn][maxs],fail[maxn],match[maxn];
    int sz,root;
    int newnode()
    {
        memset(nxt[sz],0,sizeof(nxt[sz]));
        match[sz]=0;
        return sz++;
    }
    void init()
    {
        sz = 0;
        root = newnode();
    }
    void insert(char *s){
        int u=root,n=strlen(s);
        for(int i=0; i<n; i++){
            int pos = id[s[i]];
            if(!nxt[u][pos]){
                nxt[u][pos] = newnode();
            }
            u = nxt[u][pos];
        }
        match[u] = 1;
    }
    void build()
    {
        queue<int>q;
        match[root]=fail[root]=root;
        int u;
        for(int i=0; i<n; i++){
            int &v = nxt[root][i];
            if(v){
                fail[v] = 0;
                q.push(v);
            }else{
                v = root;
            }
        }
        while(q.size()){
            u = q.front();q.pop();
            for(int i=0; i<n; i++){
                int &v = nxt[u][i];
                if(!v){
                    v = nxt[fail[u]][i];
                    continue;
                }
                q.push(v);
                fail[v] = nxt[fail[u]][i];
                match[v] |= match[fail[v]];
            }
        }
    }
}ac;
double dp[maxn][105];
bool  vis[maxn][105];
char  str[30][30];
double p[maxn];
double dfs(int u,int L)
{
    if(!L) return 1.0;
    if(vis[u][L]) return dp[u][L];
    vis[u][L]=1;
    double &ans = dp[u][L];
    ans = 0.0;
    for(int i=0; i<n; i++){
        if(!ac.match[ac.nxt[u][i]]) ans+=p[i]*dfs(ac.nxt[u][i],L-1);
    }
    return ans;
}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        ac.init();
        scanf("%d",&m);
        for(int i=0; i<m; i++){
            scanf("%s",str[i]);
        }
        scanf("%d",&n);
        char s[20];
        for(int i=0; i<n; i++){
            scanf("%s %lf",s,&p[i]);
            id[s[0]] = i;
        }
        for(int i=0; i<m; i++){
            ac.insert(str[i]);
        }
        ac.build();
        int L;
        scanf("%d",&L);
        memset(vis,0,sizeof(vis));
        double ans = dfs(0,L);
        printf("Case #%d: %.6lf\n",cas++,ans);
    }
    return 0;
}