有一只猴子随机敲键盘，给出它可能敲的键以及敲各个键的概率。
输入：n，表示有多少个键,m，表示猴子会敲m次键
n个二元组（字母，数字）
表示键代表的字母及其被敲的概率。
最后一个目标字符串。
问这只猴子敲了m次键后得到的字符串包含目标字符串的概率。
最主要的还是怎么定义出具有无后效性的状态。
用dp[i][j]表示扫描第i位，前面未曾出现完全匹配并且后缀与target已匹配长度为j的概率
然后模仿kmp匹配的过程进行dp就可以了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=;
const int MAXLEN=;
int n,m;
double p[MAXN];
char target[];
double dp[MAXLEN][]; //dp[i][j]表示扫描第i位，前面未曾出现完全匹配&&后缀与target已匹配长度为j的概率
int nxt[];
double ans;
void init()
{
for(int i=;i<MAXN;++i) p[i]=0.0;
ans=;
for(int i=;i<=m;++i)
{
for(int j=;j<;++j)
{
dp[i][j]=0.0;
}
}
dp[][]=1.0;
}
void Input()
{
char c,t;
for(int i=;i<=n;++i)
{
scanf("%c%c",&t,&c);
cin>>p[c-'a'];
}
scanf("%s",target);
}
void getnxt(char P[])
{
nxt[]=;
int len=strlen(P),k=;
for(int i=;i<len;++i)
{
while(k&&P[i]!=P[k]) k=nxt[k-];
if(P[i]==P[k]) ++k;
nxt[i]=k;
}
}
void work()
{
int len=strlen(target);
getnxt(target);
for(int i=;i<=m;++i)
{
for(int k=;k<;++k)
{
for(int j=;j<=len;++j)
{
int now=j-;
while(now&&target[now]!=k+'a') now=nxt[now-];
if(target[now]==k+'a')
{
dp[i][now+]+=dp[i-][j-]*p[k];
}
else dp[i][]+=dp[i-][j-]*p[k];
}
}
ans+=dp[i][len];
}
}
int main()
{
while(scanf("%d%d",&n,&m)==&&(n+m))
{
init();
Input();
work();
printf("%.2f%%\n",*ans);
}
return ;
}