题意为一只猴子随机输入字符串，每个字母的概率已经给出。

求猴子输入长度为N的字符串S1包含模式串S2的概率。

 

很有趣的KMP题目，在Matrix67博客里看过类似的文章，一下子就想起来了。

博客里应该说的很明白了。一个利用next数组进行dp的过程。

dp[i][j]表示输入第i个字符模式串匹配到第j个字符的概率。

然后从上往下dp。。O(n)的状态转移

对于每个状态，枚举下一个输入的字符c，设概率为p

kmp中，母串每后移一个字符，模式串指针的位置仅由新字符决定。

可以根据kmp匹配过程计算出新的j的值。设为j2

则dp[i+1][j2]+=dp[i][j]*p;

最后的答案为 ans=dp[1..n][j]

即任意位置得母串匹配到模式串结束位置的概率和。

#include 
      
       #include 
       
        #include 
        
         using namespace std; const int MAXN = 30;char s[MAXN];int F[MAXN];int M,N,L;char c[MAXN];double p[MAXN]; void callnext(){    F[1]=0;    int j=0;    for (int i=2;i<=L;i++){        while(j && s[j+1]!=s[i]) j=F[j];        if (s[j+1]==s[i]) j++;        F[i]=j;    }} double dp[1010][MAXN]; int main(){    freopen("in.txt","r",stdin);    while(1){        memset(dp,0,sizeof(dp));        scanf("%d%d\n",&M,&N);        if (!M&&!N) break;        for (int i=1;i<=M;i++) scanf("%c %lf\n",&c[i],&p[i]);        scanf("%s",s+1);        L = strlen(s+1);        callnext();        dp[0][0]=1;        for (int i=0;i