@superbin
厄....我的方法比較笨，建立自動機搞的
/*
題意：一只猴子要打長度為m的字，他會打n種字母，每種概率p[i]
問最后打出包含目標串的概率
對目標串建立AC自動機
然后dp[len,j]表示長度為len，在節(jié)點j的概率
初始dp[0,1] = 1.0
然后枚舉下一步打的字母轉(zhuǎn)移即可了
最后答案就是 1 - 不包含目標串的概率
為了不包含目標串，算的時候那個危險節(jié)點不能走
*/
#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節(jié)點處
{
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;
}