用把失配边也加到正常边以后AC自动机，状态是长度递减的DAG，每次选一个不会匹配字符的转移。

dp[u][L]表示当前在tire树上u结点长度还剩L时候不匹配的概率，根据全概率公式跑记忆化搜索。

#include
     
      using namespace std;typedef double ld;const int maxnds = 21*21, sigma_size = 62;int nds;int ch[maxnds][sigma_size];double p[sigma_size];int f[maxnds];int id[256];bool val[maxnds];int N;void getF(){    queue
      
        q;    f[0] = 0;    for(int c = 0; c < sigma_size; c++){        int u = ch[0][c];        if(u) { q.push(u); f[u] = 0; }    }    while(q.size()){        int r = q.front(); q.pop();        for(int c = 0; c < sigma_size; c++){            int u = ch[r][c];            if(!u) {                ch[r][c] = ch[f[r]][c]; continue;            }            q.push(u);            int v = f[r];            while(v && !ch[v][c]) v = f[v];            f[u] = ch[v][c];            val[u] |= val[f[u]];        }    }}void add(char *s){    int n = strlen(s), u = 0;    for(int i = 0; i < n; i++){        int c = id[s[i]];        if(!ch[u][c]){            memset(ch[nds],0,sizeof(ch[nds]));            val[nds] = false;            ch[u][c] = nds++;        }        u = ch[u][c];    }    val[u] = true;}const int maxL = 101;ld dp[maxnds][maxL];bool vis[maxnds][maxL];bool exist[sigma_size];ld dfs(int u,int L){    if(!L) return 1;    if(vis[u][L]) return dp[u][L];    vis[u][L] = true;    ld &ret = dp[u][L];    ret = 0;    for(int i = 0; i < sigma_size; i++)if(exist[i]){        if(!val[ch[u][i]]) ret += p[i]*dfs(ch[u][i],L-1);    }    return ret;}int id_cnt;void init(){    memset(ch[0],0,sizeof(ch[0]));    nds = 1;    val[0] = false;    memset(exist,0,sizeof(exist));}#define cerid ,cout<
       
        <
        
         >T;    int kas = 0;    while(T--){        init();        int K; scanf("%d",&K);        for(int i = 0; i < K; i++){            scanf("%s",temp);            add(temp);        }        scanf("%d",&N);        for(int i = 0; i < N; i++){            scanf("%s",temp);            scanf("%lf",p+id[*temp]);            exist[id[*temp]] = true;        }        getF();        int L; scanf("%d",&L);        memset(vis,0,sizeof(vis));        printf("Case #%d: %lf\n",++kas,dfs(0,L));    }    return 0;}