题意 字符集中有一些字符（最多26个），给出每个字符的出现概率（它们的和保证为1） 再给出一个子串B，长为M 求：任给一个长度为N的字符串A（只能包含字符集中的字符），使得B是A的子串的概率。 N<=100
解法 DP 想象一边随机生成字符串A，一边用KMP匹配字符串B的过程 f[i][j]表示随机生成到第i位，此时B串匹配到第j位的概率 枚举下一位生成字符c，设其生成概率为gc 假设下一位填c，计算出KMP匹配指针j应该移动到j‘ f[i+1][j’] += f[i][j]*gc 已经匹配到第m位的状态不再进行转移 ans = ∑f[i][m]
一道比较简单的概率DP结合了KMP非常的巧妙。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; double f[1010][30],ll,gl[30]; int nxt[30],n,m,l; char w[30],ch,c[30]; void calc_w() { nxt[1]=0; l=strlen(w+1); int j=0; for (int i=2;i<=l;i++) { while (j&&w[i]!=w[j+1])j=nxt[j]; if (w[j+1]==w[i])j++; nxt[i]=j; } } int main() { while(1) { memset(f,0,sizeof(f)); f[0][0]=1; scanf("%d%d\n",&n,&m); if (!n&&!m)break; for (int i=1;i<=n;i++) scanf("%c %lf\n",&c[i],&gl[i]); scanf("%s",w+1); calc_w(); for (int i=0;i<m;i++) { for (int j=0;j<l;j++) { for (int k=1;k<=n;k++) { int po=j; while (po&&w[po+1]!=c[k])po=nxt[po]; if (w[po+1]==c[k])po++; f[i+1][po]+=f[i][j]*gl[k]; } } } double ans=0; for (int i=0;i<=m;i++) ans+=f[i][l]; printf("%.2f%%\n",ans*100); } }