@superbin
厄....我的方法比较笨，建立自动机搞的
/*
题意：一只猴子要打长度为m的字，他会打n种字母，每种概率p[i]
问最后打出包含目标串的概率
对目标串建立AC自动机
然后dp[len,j]表示长度为len，在节点j的概率
初始dp[0,1] = 1.0
然后枚举下一步打的字母转移即可了
最后答案就是 1 - 不包含目标串的概率
为了不包含目标串，算的时候那个危险节点不能走
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
const double EPS = 1e-5;
double dp[2][MAXN];
double p[26];
struct Node
{
Node *ch[26] , *next;
int match , id;
}nodes[MAXN] , *Trie,*SuperRoot;
int alloc;
Node *newNode()
{
memset(&nodes[alloc] , 0 , sizeof(nodes[0]));
nodes[alloc].id = alloc;
return &nodes[alloc++];
}
void insert(Node *root ,char *s)
{
if(*s==0)root->match = 1;
else
{
if(root->ch[*s-'a'] == 0)root->ch[*s-'a'] = newNode();
insert(root->ch[*s-'a'] , s+1);
}
}
void buildTrie()
{
for(int i = 0 ; i < 26 ;i++)SuperRoot->ch[i] = Trie;
Trie->next = SuperRoot;
queue<Node*>Q;
Q.push(Trie);
while(!Q.empty())
{
Node *p = Q.front() ; Q.pop();
for(int i = 0 ; i < 26 ; i++)
{
if(p->ch[i])
{
p->ch[i]->next = p->next->ch[i];
Q.push(p->ch[i]);
}
else p->ch[i] = p->next->ch[i];
}
}
}
char str[1010];
int main()
{
// freopen("in","r",stdin);
// freopen("out","w",stdout);
int n ,m;
while( scanf("%d%d",&n,&m) , n||m)
{
memset(p,0,sizeof(p));
for(int i = 0 ; i< n; i++)
{
char ch;
scanf(" %c",&ch);
scanf("%lf",&p[ch-'a']);
}
scanf("%s",str);
alloc = 0;
SuperRoot = newNode();
Trie = newNode();
insert(Trie,str);
buildTrie();
int pre = 0 , next = 1;
for(int j = 0 ; j < alloc;j++)
dp[pre][j] = 0.0;
dp[pre][1] = 1.0;
for(int i = 0 ; i < m ; i++)
{
for(int j= 0 ; j < alloc;j++)
{
dp[next][j] = 0.0;
// printf("%d %.2f\n",j,dp[pre][j]);
}
//puts("");
for(int j = 1 ; j < alloc-1 ; j++)//目标串在alloc-1节点处
{
if( dp[pre][j] < EPS ) continue;
for(int k = 0 ; k < 26 ; k++)
{
int id = nodes[j].ch[k]->id;
dp[next][id] += dp[pre][j]*p[k];
}
}
swap(pre,next);
}
double ans = 1.0;
for(int j = 1 ; j < alloc-1 ; j++)//用1-所有不包含目标串的概率
ans -= dp[pre][j];
printf("%.2f%%\n",ans*100);
}
return 0;
}