将所有字符串建一个ac自动机，用f[i]表示随机字符串匹配到第i个字符的概率，可以转移到某些字符，如果这个点是末尾那么他只能转移到自己且概率为1，高斯消元即可
（另外还有一个有趣的做法，因为精度要求不高，可以直接对这个矩阵自乘50次得到的就是结果）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 queue<int>q; 5 int V,n,l,m,x,y,end[N],vis[N],nex[N],ch[N][N]; 6 double p[N],f[N][N]; 7 char s[N]; 8 void add(char *s,int p){ 9 int k=1; 10 for(int i=0;s[i];i++){ 11 if (!ch[k][s[i]-'A'])ch[k][s[i]-'A']=++V; 12 k=ch[k][s[i]-'A']; 13 } 14 vis[k]=1; 15 end[p]=k; 16 } 17 void build(){ 18 for(int i=1;i<=V;i++)nex[i]=1; 19 for(int i=0;i<m;i++) 20 if (ch[1][i])q.push(ch[1][i]); 21 while (!q.empty()){ 22 int k=q.front(); 23 q.pop(); 24 vis[k]|=vis[nex[k]]; 25 for(int i=0;i<m;i++) 26 if (!ch[k][i])ch[k][i]=ch[nex[k]][i]; 27 else{ 28 nex[ch[k][i]]=ch[nex[k]][i]; 29 q.push(ch[k][i]); 30 } 31 } 32 } 33 void guess(){ 34 for(int i=1;i<=V;i++){ 35 double s=fabs(f[i][i]); 36 for(int j=i+1;j<=V;j++)s=max(s,fabs(f[j][i])); 37 for(int j=i;j<=V;j++) 38 if (s==fabs(f[j][i])){ 39 s=f[j][i]; 40 for(int k=i;k<=V+1;k++)swap(f[i][k],f[j][k]); 41 break; 42 } 43 for(int j=i;j<=V+1;j++)f[i][j]/=s; 44 for(int j=1;j<=V;j++) 45 if (i!=j){ 46 s=f[j][i]; 47 for(int k=i;k<=V+1;k++)f[j][k]-=f[i][k]*s; 48 } 49 } 50 } 51 int main(){ 52 scanf("%d%d%d",&n,&l,&m); 53 for(int i=0;i<m;i++){ 54 scanf("%d%d",&x,&y); 55 p[i]=1.0*x/y; 56 } 57 V=1; 58 for(int i=1;i<=n;i++){ 59 scanf("%s",s); 60 add(s,i); 61 } 62 build(); 63 for(int i=1;i<=V;i++) 64 for(int j=0;j<m;j++) 65 if (!vis[i])f[ch[i][j]][i]+=p[j]; 66 for(int i=1;i<=V;i++)f[i][i]--; 67 f[1][V+1]=-1; 68 guess(); 69 for(int i=1;i<=n;i++)printf("%.2f ",f[end[i]][V+1]); 70 }