Infinite monkey theorem(hdu 3689)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：问随机生成一个长度为m(m<=1000)长度的字符串，出现某个子串s的概率是多少。

/*

  KMP+DP

  设f[i][j]表示A生成到第i位，此时B串匹配到第j位的概率。

  转移方程为f[i+1][k]+=f[i][j]*lv(枚举的第i位生成字符的概率)

  k位如果第i位生成该字符，那么它能和B串匹配到的地方。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 1010

using namespace std;

double lv[],dp[N][N];

char s[N],zifu[];

int n,m,len,fail[N];

void get_fail(){

    fail[]=;

    for(int i=;i<=len;i++){

        int p=fail[i-];

        while(p&&s[p+]!=s[i]) p=fail[p];

        if(s[p+]==s[i]) fail[i]=p+;

        else fail[i]=;

    }

}

void work(){

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

        char c;cin>>zifu[i];

        scanf("%lf",&lv[i]);

    }

    scanf("%s",s+);len=strlen(s+);

    get_fail();

    dp[][]=100.0;

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

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

            for(int k=;k<=n;k++){

                int p=j;

                while(p&&s[p+]!=zifu[k])p=fail[p];

                if(s[p+]==zifu[k])dp[i+][p+]+=dp[i][j]*lv[k];

                else dp[i+][]+=dp[i][j]*lv[k];

            }

    double ans=;

    for(int i=;i<=m;i++)ans+=dp[i][len];

    printf("%.2lf",ans);cout<<"%"<<endl;

}

int main(){

    while(scanf("%d%d",&n,&m)){

        if(!n&&!m)break;

        memset(fail,,sizeof(fail));

        memset(dp,,sizeof(dp));

        work();

    }

    return ;

}