題意：問隨機生成一個長度為m(m<=1000)長度的字符串，出現某個子串s的概率是多少。

解法：dp+kmp優化。ans[i][j]表示i長度，走到了s的j位置的概率，當然這是在i之前沒有出現s的前提下(在狀態轉移時候已經保證了這一點)；然后最后的概率就是1-m長度的串分別最后出現s的概率之和。

代碼：

/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std;#define eps 1e-8 #define zero(_) (_<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; int n,m; struct point {char c;double p; } points[30]; map<char,double> maps; string s; double ans[1010][12]; int Next[30]; void get_next() {int i=0;int j=Next[0]=-1;int len=s.size();while(i<len){while(j!=-1&&s[i]!=s[j]) j=Next[j];Next[++i]=++j;} } int OK(string t) {for(int i=0;i<t.size();i++){if(t.substr(i,t.size()-i)==s.substr(0,t.size()-i))return t.size()-i;}return 0; } int get(int j,int k) {while(j!=-1&&s[j]!=points[k].c){j=Next[j];}return j+1; } int main() {while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0)break;memset(ans,0,sizeof ans);for(int i=0; i<n; i++){cin>>points[i].c>>points[i].p;}cin>>s;get_next();ans[0][0]=1.0;for(int i=1; i<=m; i++){for(int j=1; j<=s.size(); j++)for(int k=0; k<n; k++){ans[i][get(j-1,k)]+=ans[i-1][j-1]*points[k].p;}}double out=0;for(int i=1;i<=m;i++)out+=ans[i][s.size()];printf("%.2lf%%\n",out*100);}return 0; }

總結

以上是生活随笔為你收集整理的hdu3689（kmp+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。