題意 字符集中有一些字符（最多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];新聞熱點
疑難解答
