首页 > 代码库 > hdu3689(kmp+dp)
hdu3689(kmp+dp)
题意:问随机生成一个长度为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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。