HDU 3689 Infinite monkey theorem —

　　这题由于是一个单词，其实直接kmp+dp也无妨。建立自动机当然也是可以的。设dp[i][j]表示匹配到第i个字母的时候，在单词中处于第j个位置的概率，因此最终的答案是dp[0~m][len]，m是输入的长度，len是单词的长度。转移方程见代码，即在一个节点的位置时，枚举下一步的走法，乘以这种走法的概率即是对下一个状态的概率贡献。

　　其实自动机的fail指针跳转的位置即是kmp中nxt数组跳转的位置。

　　代码如下：

     {

         while(j && word[j+] != word[i]) j = nxt[j];

         if(word[j+] == word[i]) j++;

         nxt[i] = j;

     }

 }

 int main()

 {

     while(scanf("%d%d",&n,&m) == )

     {

         if(n== && m==) break;

         char s[];

         for(int i=;i<=n;i++)

         {

             scanf("%s%lf",s,p+i);

             c[i] = s[];

         }

         scanf("%s",word+);

         len = strlen(word+);

         get_nxt();

         memset(dp,,sizeof dp);

         dp[][] = 1.0;

         for(int i=;i<m;i++)

         {

             for(int j=;j<len;j++)

             {

                 for(int k=;k<=n;k++)

                 {

                     int pos = j;

                     while(pos && word[pos+] != c[k]) pos = nxt[pos];

                     if(word[pos+] == c[k]) pos++;

                     dp[i+][pos] += dp[i][j] * p[k];

                 }

             }

         }

         double ans = 0.0;

         for(int i=;i<=m;i++) ans += dp[i][len];

         printf("%.2f%%\n",ans*100.0);

     }

     return ;

 }

kmp+dp

 #include <bits/stdc++.h>

 using namespace std;

 const int MAX_Tot =  + ;

 int n,m,len;

 double p[];

 char word[];

 int nxt[];

 double dp[][];

 struct Aho

 {

     struct state

     {

         int nxt[];

         int fail,cnt;

     }stateTable[MAX_Tot];

     int size;

     queue<int> que;

     void init()

     {

         while(que.size()) que.pop();

         for(int i=;i<MAX_Tot;i++)

         {

             memset(stateTable[i].nxt,,sizeof(stateTable[i].nxt));

             stateTable[i].fail = stateTable[i].cnt = ;

         }

         size = ;

     }

     void insert(char *s)

     {

         int n = strlen(s);

         int now = ;

         for(int i=;i<n;i++)

         {

             char c = s[i];

             if(!stateTable[now].nxt[c-'a'])

                 stateTable[now].nxt[c-'a'] = size++;

             now = stateTable[now].nxt[c-'a'];

         }

         stateTable[now].cnt++;

     }

     void build()

     {

         stateTable[].fail = -;

         que.push();

         while(que.size())

         {

             int u = que.front();que.pop();

             for(int i=;i<;i++)

             {

                 if(stateTable[u].nxt[i])

                 {

                     if(u == ) stateTable[stateTable[u].nxt[i]].fail = ;

                     else

                     {

                         int v = stateTable[u].fail;

                         while(v != -)

                         {

                             if(stateTable[v].nxt[i])

                             {

                                 stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];

                                 break;

                             }

                             v = stateTable[v].fail;

                         }

                         if(v == -) stateTable[stateTable[u].nxt[i]].fail = ;

                     }

                     que.push(stateTable[u].nxt[i]);

                 }

                 /*****建立自动机nxt指针*****/

                 else

                 {

                     if(u == ) stateTable[u].nxt[i] = ;

                     else

                     {

                         int p = stateTable[u].fail;

                         while(p != - && stateTable[p].nxt[i] == ) p = stateTable[p].fail;

                         if(p == -) stateTable[u].nxt[i] = ;

                         else stateTable[u].nxt[i] = stateTable[p].nxt[i];

                     }

                 }

                 /*****建立自动机nxt指针*****/

             }

         }

     }

 }aho;

 int main()

 {

     while(scanf("%d%d",&n,&m) == )

     {

         if(n== && m==) break;

         aho.init();

         char s[];

         memset(p,,sizeof p);

         for(int i=;i<=n;i++)

         {

             double t;

             scanf("%s%lf",s,&t);

             p[s[]-'a'] = t;

         }

         scanf("%s",word+);

         aho.insert(word+); aho.build();

         memset(dp,,sizeof dp);

         dp[][] = 1.0;

         int sz = aho.size-;

         for(int i=;i<m;i++)

         {

             for(int j=;j<sz;j++)

             {

                 for(int k=;k<;k++)

                 {

                     int v = aho.stateTable[j].nxt[k];

                     dp[i+][v] += dp[i][j] * p[k];

                 }

             }

         }

         double ans = 0.0;

         for(int i=;i<=m;i++) ans += dp[i][sz];

         printf("%.2f%%\n",ans*100.0);

     }

     return ;

 }

自动机+dp

巴特西

HDU 3689 Infinite monkey theorem ——（自动机+DP）

最新文章

热门文章