注意 是0<=P, n , l, m≤ 10.

input 1
3 2 2
1 2
1 2
AB
BA
AA

input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA

output 1
0.25
0.50
0.25

output 2
0.31
0.33
0.37

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (208)

 using namespace std;

 int n,m,l,tar[N];

 int sz,Son[N][],Fail[N],End[N];

 double x,y,p[N];

 char s[N];

 queue<int>q;

 struct Matrix

 {

     double m[N][N];

     Matrix(){memset(m,,sizeof(m));}

     Matrix operator * (const Matrix &b) const

     {

         Matrix c;

         for (int i=; i<=sz; ++i)

             for (int j=; j<=sz; ++j)

                 for (int k=; k<=sz; ++k)

                     c.m[i][j]+=m[i][k]*b.m[k][j];

         return c;

     }

 }A;

 void Insert(char s[],int id)

 {

     int now=;

     for (int i=; i<l; ++i)

     {

         int c=s[i]-'A';

         if (!Son[now][c]) Son[now][c]=++sz;

         now=Son[now][c];

     }

     End[now]++; tar[id]=now;

 }

 void Build_Fail()

 {

     for (int i=; i<m; ++i)

         if (Son[][i]) q.push(Son[][i]);

     while (!q.empty())

     {

         int now=q.front(); q.pop();

         for (int i=; i<m; ++i)

         {

             if (!Son[now][i])

             {

                 Son[now][i]=Son[Fail[now]][i];

                 continue;

             }

             Fail[Son[now][i]]=Son[Fail[now]][i];

             q.push(Son[now][i]);

         }

     }

 }

 void Solve()

 {

     for (int i=; i<=sz; ++i)

     {

         if (End[i]) A.m[i][i]=;

         else for (int j=; j<m; ++j) A.m[i][Son[i][j]]+=p[j];

     }

     for (int i=; i<=; ++i) A=A*A;

     for (int i=; i<=n; ++i)

         printf("%.2lf\n",A.m[][tar[i]]);

 }

 int main()

 {

     scanf("%d%d%d",&n,&l,&m);

     for (int i=; i<m; ++i)

         scanf("%lf%lf",&x,&y), p[i]=x/y;

     for (int i=; i<=n; ++i)

         scanf("%s",s), Insert(s,i);

     Build_Fail(); Solve();

 }