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

題意：給定n(<=8)個單詞和一個長度L(<=14)

問隨機(jī)寫一個L長度的字符串(a..z等概率出現(xiàn))，出現(xiàn)所給單詞個數(shù)的期望。

兩種思路：

------------KMP------------

分別求每一個單詞出現(xiàn)的概率相加即可。

求一個單詞出現(xiàn)的概率不好求，可以轉(zhuǎn)化為求其不出現(xiàn)的概率

對于某給定單詞s，

用dp[i][j][k] 表示長度為i的隨機(jī)字符串最后一個字符為k，最后k個字符與s[1..k]相等的概率

轉(zhuǎn)移的時候控制k<|s|就可以保證s在隨機(jī)字符串中不出現(xiàn)。

轉(zhuǎn)移的時候要用到kmp，因?yàn)殡S機(jī)字符串加上的字符后可能導(dǎo)致和s[k+1]不匹配

這時候要用kmp來跳到一個合適的匹配位置。

例如，s = "abaa",?

有狀態(tài)dp[i][3]['a'], 表示長度為i的隨機(jī)字符串后3個字符為"aba"

現(xiàn)在在后面加一個字符'b', 得到四個字符"abab", 和s匹配的長度變成了2

所以要轉(zhuǎn)移到dp[i+1][2]['b']

#include <cstdio> #include <cstring> using namespace std; const double PP = 1.0/26.0; const double eps = 1e-8; int n, L; int next[20], a[20]; double f[20][30][30]; char s[20]; double solve(char s[]){int n = strlen(s+1);for (int i=1; i<=n; i++) a[i] = s[i]-'a';next[1] = 0;for (int i=2; i<=n; i++){int j = next[i-1];while (j && a[j+1] != a[i]) j = next[j];if (a[j+1] == a[i]) j++;next[i] = j;}memset(f, 0, sizeof(f));for (int c=0; c<26; c++)f[1][c][c==a[1]] = PP;for (int i=1; i<L; i++)for (int j=0; j<26; j++)for (int k=0; k<n&&k<=i; k++) if (f[i][j][k]>eps){for (int c=0; c<26; c++){int nxtj = k;while (nxtj && a[nxtj+1]!=c) nxtj = next[nxtj];if (a[nxtj+1] == c) nxtj++;f[i+1][c][nxtj] += f[i][j][k]*PP;}}double val = 0;for (int j=0; j<26; j++)for (int k=0; k<n; k++)val += f[L][j][k];return 1.0-val; } int main(){int test;scanf("%d", &test);for (int T=1; T<=test; T++){double ans = 0;scanf("%d %d", &n, &L);for (int i=1; i<=n; i++){scanf("%s", s+1);ans += solve(s);}printf("%.6lf\n", ans+eps);}return 0; }

------------AC自動機(jī)------------

用n個字符串建一個自動機(jī)，單詞結(jié)尾出的節(jié)點(diǎn)存下單詞編號。

然后從根節(jié)點(diǎn)開始走，

dp[i][j][k]表示走i步, 走到j(luò), 經(jīng)過了k這些單詞, k是二進(jìn)制數(shù)

最后答案等于 sigma(dp[L][j][k] * bit(k)), bit(k)表示k中1的個數(shù)。

總結(jié)

以上是生活随笔為你收集整理的whu1572 Cyy and Fzz[字符串+概率]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。