题意：问随机生成一个长度为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[30],dp[N][N]; char s[N],zifu[30]; int n,m,len,fail[N]; void get_fail(){ fail[1]=0; for(int i=2;i<=len;i++){ int p=fail[i-1]; while(p&&s[p+1]!=s[i]) p=fail[p]; if(s[p+1]==s[i]) fail[i]=p+1; else fail[i]=0; } } void work(){ for(int i=1;i<=n;i++){ char c;cin>>zifu[i]; scanf("%lf",&lv[i]); } scanf("%s",s+1);len=strlen(s+1); get_fail(); dp[0][0]=100.0; for(int i=0;i<m;i++) for(int j=0;j<len;j++) for(int k=1;k<=n;k++){ int p=j; while(p&&s[p+1]!=zifu[k])p=fail[p]; if(s[p+1]==zifu[k])dp[i+1][p+1]+=dp[i][j]*lv[k]; else dp[i+1][0]+=dp[i][j]*lv[k]; } double ans=0; for(int i=1;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,0,sizeof(fail)); memset(dp,0,sizeof(dp)); work(); } return 0; }