题目描述：
大概的意思就是根据无限猴子定理，无限只猴子坐在打字机旁瞎敲，总有一个能敲出莎士比亚文集。现在给你一个打字机和一只猴子，打字机的每个按钮（共n个）上的字母及猴子按下这个按钮的概率已知，而且猴子只能按m下按钮，又给定一个串，问猴子打出的乱码中含这个串的概率。
其中n<=26,m<=1000，多组数据，以n=0，m=0结束。以百分数形式输出，保留小数点后2位。
样例：
输入：
4 10
w 0.25
o 0.25
r 0.25
d 0.25
word
2 10
a 1.0
b 0.0
abc
2 100
a 0.312345
b 0.687655
abab
0 0
输出：
2.73%
0.00%
98.54%
解题思路：
对于第一组数据（work）
很显然算法是：0.25*0.25*0.25*0.25*7*100%=2.73%;
而对于第三组（abab）就不成立了，为什么呢？
显然是因为第一组没有重复的字母出现，也就是说，如果你的猴子恰好打下了aba，然后它又不幸地打下了a那么也不算太糟，至少你只需要再打一个bab就可以完成任务了。而对于第一只猴子就没有那么幸运了，如果它打下了wor又不幸地打下了r，那么它必须再打下work才能完成任务。
也就是说，即使你打下了错误的字母，你也有可能创造了一个前缀。
所以说我们只需要求出一个错误的字符创造出的前缀是谁，就可以更新这个前缀出现的概率了。
那么考虑用dp[i][j]表示在猴子打下第i个字母时字符串完成到j的匹配的概率。
而这个由错误创造的前缀是谁，这是不是KMP。
然而这和普通的KMP不一样，或者我学了假的KMP，这次kmp的next数组存的是这个模式串第i位的值对应存在的前缀的位置，也就是说，这次是成功指针，而非失配指针。
dp方程就出来了：dp[这一次敲击][最长匹配的新字符最长前缀]=∑dp[上一次敲击][最长匹配]（枚举新字符是谁，再进行前缀操作）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int l;
bool JDr_is_Handsome=true;
char cmd[];
char a[];
int op[];
int nxt[];
double p[];
double dp[][];
int main()
{
while(JDr_is_Handsome)
{
scanf("%d%d",&n,&m);
if(!n&&!m)
return ;
memset(dp,,sizeof(dp));
memset(p,,sizeof(p));
for(int i=;i<=n;i++)
{
scanf("%s",cmd+);
op[i]=cmd[];
scanf("%lf",&p[i]);
}
scanf("%s",a+);
l=strlen(a+);
nxt[]=;
for(int i=,j=;i<=l;)
{
while(j&&a[j+]!=a[i])j=nxt[j];
if(a[j+]==a[i])j++;
nxt[i]=j;
i++;
}
dp[][]=1.00;
for(int i=;i<=m;i++)
{
for(int j=;j<l;j++)
{
for(int k=;k<=n;k++)
{
int pos=j;
while(pos&&a[pos+]!=op[k])
pos=nxt[pos];
if(a[pos+]==op[k])pos++;
dp[i][pos]+=dp[i-][j]*p[k];
}
}
}
double ans=;
for(int i=l;i<=m;i++)
ans+=dp[i][l];
printf("%.2lf%%\n",ans*100.00);
}
return ;
}