【hdu3689】 Infinite monkey theorem

2019-11-14 09:20:10

字體：大中小

供稿：網(wǎng)友

題意字符集中有一些字符（最多26個(gè)），給出每個(gè)字符的出現(xiàn)概率（它們的和保證為1）再給出一個(gè)子串B，長(zhǎng)為M 求：任給一個(gè)長(zhǎng)度為N的字符串A（只能包含字符集中的字符），使得B是A的子串的概率。 N<=100

解法 DP 想象一邊隨機(jī)生成字符串A，一邊用KMP匹配字符串B的過(guò)程 f[i][j]表示隨機(jī)生成到第i位，此時(shí)B串匹配到第j位的概率枚舉下一位生成字符c，設(shè)其生成概率為gc 假設(shè)下一位填c，計(jì)算出KMP匹配指針j應(yīng)該移動(dòng)到j(luò)‘ f[i+1][j’] += f[i][j]*gc 已經(jīng)匹配到第m位的狀態(tài)不再進(jìn)行轉(zhuǎn)移 ans = ∑f[i][m]

一道比較簡(jiǎn)單的概率DP結(jié)合了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];