hdu3689（kmp+dp） - c++编程基础

题意：问随机生成一个长度为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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //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
              
                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
               
                >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