題目鏈接：http://vjudge.net/contest/142513#problem/A

題意：給出一些字符和各自對應的選擇概率,隨機選擇L次后將得到一個長度為L的隨機字符串S.給出K個模版串,計算S不包含任何一個串的概率.

?

分析：

?在構造好的AC自動機里面，每隨機生成一個字母，相當于在AC自動機中隨機走一步。所有單詞結點標記為禁止，本題就是從結點 0 走 l 步，不進入任何禁止結點的概率。

#include <bits/stdc++.h> using namespace std;const int SIGMA_SIZE = 64; const int MAXNODE = 500;int idx[256]; char s[30][30]; double prob[SIGMA_SIZE]; int n;struct AhoCorasickAutomata {int ch[MAXNODE][SIGMA_SIZE];int f[MAXNODE];int match[MAXNODE];int sz;void init(){sz = 1;memset(ch[0],0,sizeof(ch[0]));}void insert(char *s){int u = 0,n = strlen(s);for(int i=0; i<n; i++){int c = idx[s[i]];if(!ch[u][c]){memset(ch[sz],0,sizeof(ch[sz]));match[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}match[u] = 1;}void getFail(){queue<int> q;f[0] = 0;for(int c=0; c<SIGMA_SIZE; c++){int u = ch[0][c];if(u){f[u] = 0;q.push(u);}}while(!q.empty()){int r = q.front();q.pop();for(int c=0; c<SIGMA_SIZE; c++){int u = ch[r][c];if(!u){ch[r][c]=ch[f[r]][c];continue;}q.push(u);int v = f[r];while(v&&!ch[v][c])v = f[v];f[u] = ch[v][c];match[u] |=match[f[u]];}}} };AhoCorasickAutomata ac;double d[MAXNODE][105]; int vis[MAXNODE][105];double getProb(int u,int l) {if(!l) return 1.0;if(vis[u][l]) return d[u][l];vis[u][l] = 1;double& ans = d[u][l];ans = 0.0;for(int i=0; i<n; i++){if(!ac.match[ac.ch[u][i]])ans += prob[i]*getProb(ac.ch[u][i],l-1);}return ans; }int main() {int T;scanf("%d",&T);for(int kase = 1; kase<=T; kase ++){int k,l;scanf("%d",&k);for(int i=0; i<k; i++)scanf("%s",s[i]);scanf("%d",&n);for(int i=0; i<n; i++){char ch[9];scanf("%s%lf",ch,&prob[i]);idx[ch[0]] = i;}ac.init();for(int i=0; i<k; i++)ac.insert(s[i]);ac.getFail();scanf("%d",&l);memset(vis,0,sizeof(vis));printf("Case #%d: %.6lf\n",kase,getProb(0,l));}return 0; }

?

轉載于:https://www.cnblogs.com/TreeDream/p/6087297.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的AC自动机——Uva 11468 子串的全部內容，希望文章能夠幫你解決所遇到的問題。

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