題目：http://acm.whu.edu.cn/land/problem/detail?problem_id=1572

題意: ?有n個目標串，長度均小于15，（n<=8），現在隨機寫一個長度為L的字符串，問寫下的這個字符串包含目標串的期望的個數。

比賽的時候還以為是水題，其實是自己太水。這種題一般是AC自動機的中等題，本題也可以用KMP做，結合狀壓dp。

方法一：AC自動機

建完Trie樹后，就是跑一遍dp，注意單詞節點要 |=(1<<val)，會有重的字符串。

dp過程： 用 dp[i][j][k] 表示在自動機節點i，當前剩余j步，已包含狀態為k(k為二進制數)的概率。

轉移就是 枚舉下一個字符，由當前i點會沿著next數組走向now= next[i][ch]

dp[now][j-1][ k|end[now] ] += dp[i][j][k] * (1.0/26)

最后統計就可以了。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int MAX_N = 105; const int ALP = 26; const int N = 15; struct Trie{int next[MAX_N][ALP] , fail[MAX_N] , end[MAX_N];int root , L ;int newnode(){for(int i=0;i<ALP;i++)next[L][i] = -1;end[L++] = 0;return L-1;}void init(){memset(end,0,sizeof(end));L = 0;root = newnode();}void insert(char* buf , int id){int now = root;int len = strlen(buf);for(int i=0;i<len;i++){int ch = buf[i]-'a';if(next[now][ch]==-1)next[now][ch] = newnode();now = next[now][ch];}end[now] |= 1<<(id-1);}void build(){queue<int> Q;fail[root] = root;for(int i=0;i<ALP;i++)if(next[root][i]==-1)next[root][i] = root;else{fail[next[root][i]] = root;Q.push(next[root][i]);}while(!Q.empty()){int now = Q.front(); Q.pop();for(int i=0;i<ALP;i++){if(next[now][i]==-1)next[now][i] = next[fail[now]][i];else{fail[next[now][i]] = next[fail[now]][i];Q.push(next[now][i]);}}}}double dp[MAX_N][N][(1<<8)+5];double get_ans(int n,int step){for(int i=step;i>=0;i--)for(int j=0;j<L;j++)for(int k=0;k<(1<<n);k++) dp[j][i][k] = 0;dp[0][step][0] = 1.0;for(int i=step;i>=1;i--)for(int j=0;j<L;j++)for(int k=0;k<(1<<n);k++)if(dp[j][i][k]>0)for(int p=0;p<26;p++){int now = next[j][p];int state = 0;int tmp = now;while(tmp!=root){state |= end[tmp];tmp = fail[tmp];}dp[now][i-1][k|state] += dp[j][i][k]*(1.0/26);}double ret = 0;for(int i=0;i<L;i++)for(int k=1;k<(1<<n);k++)if(dp[i][0][k]>0){int ep = 0;for(int p=0;p<n;p++) if(k&(1<<p))ep++; // printf("node %d state %d num %d p=%f\n",i,k,ep,dp[i][0][k]);ret += ep*dp[i][0][k];}return ret;} }ac;char s[15]; int main(){int T,n,L;cin >> T;while(T--){scanf("%d%d",&n,&L);ac.init();for(int i=1;i<=n;i++){scanf("%s",s);ac.insert(s,i);}ac.build(); // printf("numL = %d n L %d %d\n",ac.L,n,L);double ans = ac.get_ans(n,L);printf("%.6f\n",ans);}return 0; }

-----------------------------------------------------

方法二：KMP

由于每個目標串之間是獨立的，所以可以單獨統計每個目標串出現的期望，累加就可以。

那么對于單個串只需得到 ?不能包含它的概率就可以了 ，它的貢獻就是1-p。

同樣也是dp： dp[i][j]表示匹配到第i位（i未匹配成功）還剩余j步，不能包含此串的概率。

轉移就是 枚舉下一個字符，沿fail函數走到最大匹配位置的下一位置now

dp[now][j] += dp[i][j] * (1.0/26)

對于每一個目標串統計貢獻和。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 20; struct KMP{char P[MAX_N];int fail[MAX_N],len;void get_fail(){len = strlen(P);fail[0] = fail[1] = 0;for(int i=1;i<len;i++){int j = fail[i];while(j && P[j]!=P[i]) j = fail[j];fail[i+1] = P[j]==P[i] ? j+1 : 0;}}double dp[MAX_N][15];double get_ans(int L){memset(dp,0,sizeof(dp));dp[0][L] = 1.0;for(int i=L;i>=1;i--)for(int j=0;j<len;j++){for(int k=0;k<26;k++){if(j==len-1 && P[len-1]=='a'+k) continue;int now = j;if(P[j]=='a'+k) now = j+1;else{while(now && P[now]!='a'+k) now = fail[now];if(P[now]=='a'+k) now++;}dp[now][i-1] += dp[j][i]*(1.0/26);}}double ans = 1.0;for(int i=0;i<len;i++)ans -= dp[i][0];return ans;} }km;int main(){int T,n,L;cin >> T;while(T--){scanf("%d%d",&n,&L);double ans = 0;for(int i=1;i<=n;i++){scanf("%s",km.P);km.get_fail();ans += km.get_ans(L);}printf("%.6f\n",ans);}return 0; }

通過這道題還是更加深入的理解了KMP 和AC自動機。

總結

以上是生活随笔為你收集整理的woj1572 Cyy and Fzz KMP / AC自动机 + DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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