这道题还比较友好~
首先，构建出来 $AC$ 自动机，那么我们要求的就是从 $0$ 号点走无限次走到一个终止节点的概率.
考虑构建转移矩阵 $M,$ $M_{i,j}$ 表示节点 $i$ 转移到节点 $j$ 的概率.
如果 $i$ 不是终止节点，则直接将概率相加即可，否则，只有 $M_{i,i}$ 为 $1,$ 其余为 $0.$
这么做目的：
如果碰到终止节点，那整个过程应该结束，换句话说终止节点不能对其他点有贡献.
如果碰到终止节点，那整个过程应该结束，所以无论再乘几次，终止节点的概率都应当完全保留，故 $M_{i,i}=1.$
#include <bits/stdc++.h>
#define N 103
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
double perc[N],answer[N];
char str[N];
int tot;
queue<int>q;
struct Node
{
int f,ch[13],tag;
}t[N*10];
struct matrix
{
double a[N][N];
double*operator[](int x) { return a[x]; }
matrix() { memset(a,0,sizeof(a)); }
matrix friend operator*(matrix a,matrix b)
{
matrix c;
int i,j,k;
for(i=0;i<=tot;++i)
for(j=0;j<=tot;++j)
for(k=0;k<=tot;++k)
c[i][j]+=a[i][k]*b[k][j];
return c;
}
}mat;
int main()
{
// setIO("input");
int n,l,m,i,j,k;
scanf("%d%d%d",&n,&l,&m);
for(i=0;i<m;++i)
{
double a,b;
scanf("%lf%lf",&a,&b),perc[i]=1.0*a/b;
}
for(i=1;i<=n;++i)
{
int p=0;
scanf("%s",str+1);
for(j=1;j<=l;++j)
{
if(!t[p].ch[str[j]-'A']) t[p].ch[str[j]-'A']=++tot;
p=t[p].ch[str[j]-'A'];
}
t[p].tag=i;
}
for(i=0;i<m;++i) if(t[0].ch[i]) q.push(t[0].ch[i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(i=0;i<m;++i)
{
int p=t[u].ch[i];
if(!p)
{
t[u].ch[i]=t[t[u].f].ch[i];
continue;
}
t[p].f=t[t[u].f].ch[i];
q.push(p);
}
}
for(i=0;i<=tot;++i)
{
if(t[i].tag) mat[i][i]=1.00;
else for(j=0;j<m;++j) mat[i][t[i].ch[j]]+=perc[j];
}
for(i=1;i<=60;++i) mat=mat*mat;
for(i=0;i<=tot;++i) if(t[i].tag) answer[t[i].tag]=mat[0][i];
for(i=1;i<=n;++i) printf("%.2f
",answer[i]);
return 0;
}