题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1444

非权限题，就没粘贴题面了。

解法：

AC自动机+矩阵乘法

首先把模式串建成AC自动机，构建出转移矩阵。

构造方法：a[i][j]表示从第i个结点转移到第j个结点的概率，则如果j被标记过，f[i][j]=1，

否则f[i][j]=p[ch[j]]。

还有1个高斯消元的解法，纠结了好久，最后看discuss里面博主给了一个用期望高斯消元的博客，看懂了

https://blog.sengxian.com/solutions/bzoj-1444

///BZOJ 1444

#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
struct node{
    double p[maxn][maxn];
    node(){memset(p, 0, sizeof(p));}
}a;
char s[maxn];
int tree[maxn][26];
int fail[maxn];
bool word[maxn];
int n, l, m, cnt=1, id = 0;
double p[maxn];
int pos[maxn];

queue <int> q;

void ins()
{
    scanf("%s", s+1);
    int len = strlen(s+1), now=1;
    for(int i=1; i<=len; i++){
        int id=s[i]-'A';
        if(!tree[now][id]) tree[now][id]=++cnt;
        now=tree[now][id];
    }
    word[now]=1;
    pos[++id]=now;
}

void Get_fail()
{
    q.push(1);
    fail[1] = 0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        word[u] |= word[fail[u]];
        for(int i=0; i<m; i++){
            int k = fail[u];
            while(k&&!tree[k][i]) k=fail[k];
            if(tree[u][i]){
                fail[tree[u][i]] = k?tree[k][i]:1;
                q.push(tree[u][i]);
            }
            else{
                tree[u][i]=k?tree[k][i]:1;
            }
        }
    }
}

void Get_maze(){
    for(int i=1; i<=cnt; i++){
        if(word[i]) a.p[i][i]=1;
        else for(int x=0; x<m; x++){
            a.p[i][tree[i][x]]+=p[x];
        }
    }
}

node operator * (const node &a, const node &b)
{
    node res;
    for(int i=1; i<=cnt; i++){
        for(int j=1; j<=cnt; j++){
            for(int k=1; k<=cnt; k++){
                res.p[i][j] += a.p[i][k]*a.p[k][j];
            }
        }
    }
    return res;
}

int main()
{
    scanf("%d%d%d", &n,&l,&m);
    for(int i=0; i<m; i++){
        double x, y;
        scanf("%lf%lf", &x,&y);
        p[i]=x/y;
    }
    for(int i=1; i<=n; i++){
        ins();
    }
    Get_fail();
    Get_maze();
    for(int i=1; i<=100; i++) a=a*a;
    for(int i=1; i<=n; i++) printf("%.2f\n", (double)a.p[1][pos[i]]);
    return 0;
}