题目是给出K个模板串，再给出k个字符，这些字符包括了模板串里的字符，也有不是模板串里的字符，然后再给出这些字符的概率，随机选择L次后，就能得到一条L长的随机字符串，问这个随机字符串不包括任何一个模板串的概率
首先把K个模板串构造成自动机，然后把所有的结尾做一下标记，以提示该节点不可到达，因为如果走到当前结点，即意味着出现了一个模板串
然后就是根据全概率公式了，首先先来理解一下全概率公式
比如三个箱子，装了一些不同颜色但其它性质皆一样的球
箱子一：3红2蓝
箱子二：2红3蓝
箱子三：全红
问从中抽一个球，刚好抽中红球的概率
这概率=sum(选中箱子x的概率*箱子x中抽到红球的概率）
在三个箱子这个情景里，prob=1/3*(3/5)+(1/3)*(2/5)+(1/3)*1=2/3
对于这道题，设定一个状态 dp[u][l]，代表着，从当前节点U开始，选l个字符且使所形成的字符不包括模板串的概率
u的可选子节点就相当于箱子
那么，
选中箱子x的概率*箱子x中抽到红球的概率
就相当于
选中子节点c的概率*选中节点c后，选l-1个字符使所形成的字符不包括模板串的概率
不难得到状态方程
dp[u][l]=sum(dp[c][l-1]*prob[c]);
这里的得用下递归了……
接下来是几个小优化：
时间：用记忆化搜索，开vis标记是否访问过某状态，如访问过，直接返回其状态下的概率
空间：开一个match[]，合并一下val和last的值，因为我们只需要只到哪些节点是结尾，val和last标记的节点都能做结尾，把它们合并下就好
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxnode=1500;
const int sigma_size=26+26+10;
double prob[sigma_size];
double dp[maxnode][110];
typedef struct ac_automate
{
int match[maxnode], f[maxnode];
int ch[maxnode][sigma_size];
int sz;
bool vis[maxnode][110];
int idx(char x)
{
if('0'<=x&&x<='9')return x-'0';
else if('a'<=x&&x<='z')return x-'a'+10;
else return x-'A'+36;
}
void init()
{
memset(match, 0, sizeof(match));
memset(ch[0], 0, sizeof(ch[0]));
memset(vis[0], false, sizeof(vis[0]));
sz=1;
}
void insert(char *s)
{
int u=0, n=strlen(s);
for(int i=0;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz], 0, sizeof(ch[sz]));
memset(vis[sz], false, sizeof(vis[sz]));
ch[u][c]=sz++;
}
u=ch[u][c];
}
match[u]=1;
}
void getFail()
{
queue<int>q;
f[0]=0;
for(int c=0;c<sigma_size;c++)
{
int u=ch[0][c];
if(u){f[u]=0;q.push(u);match[0]=0;}
}
while(!q.empty())
{
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];
if(!match[u])match[u]=match[f[u]];
}
}
}
double getProb(int u, int L)
{
if(!L)return 1.0;
if(vis[u][L])return dp[u][L];
vis[u][L]=true;
double &ans=dp[u][L];
ans=0.0;
for(int i=0;i<sigma_size;i++)
{
int c=ch[u][i];
if(prob[i]==0)continue;
if(!match[c])ans+=prob[i]*getProb(c, L-1);
}
return ans;
}
}AhoCorasick_automata;
char P[25];
AhoCorasick_automata ac;
int main()
{
int ncase;int cnt=0;
scanf("%d", &ncase);
while(ncase--)
{
int k;
ac.init();cnt++;
for(int i=0;i<sigma_size;i++)prob[i]=0;
scanf("%d", &k);
while(k--)
{
scanf("%s", P);
ac.insert(P);
}
int n;double pro;scanf("%d", &n);
while(n--)
{
scanf("%s%lf", P, &pro);
int id=ac.idx(P[0]);
prob[id]=pro;
}
ac.getFail();
int l;scanf("%d", &l);
printf("Case #%d: %.6lf\n", cnt, ac.getProb(0, l));
}
return 0;
}