https://vjudge.net/problem/UVA-11468
给出一些字符和各自对应的选择概率，随机选择L次后得到一个长度为L的随机字符串S。
给出K个模板串，计算S不包含任何一个模板串的概率
dp[i][j]表示现在在AC自动机的i号点，还需要走j步的概率
dp[i][j]=Σdp[k][j-1] ，k不是单词节点
注意：
1、模板串可能是模板串的后缀，所以这题要用AC自动机，而不是Trie
2、在构造失配指针时，如果边不存在，要补上，边（不是失配指针）指向父节点的失配指针的子节点
#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; char s[21]; int len,tot,trie[21*21][63]; bool mark[21*21],v[21*21][21*21]; double p[21*21],dp[21*21][21*21]; char ch[21*21]; int f[21*21]; int n; queue<int>q; int get(char c) { if(c>='0'&&c<='9') return c-'0'; if(c>='a'&&c<='z') return c-'a'+10; return c-'A'+36; } void insert() { len=strlen(s); int root=1,id; for(int i=0;i<len;i++) { id=get(s[i]); if(!trie[root][id]) { trie[root][id]=++tot; memset(trie[tot],0,sizeof(trie[tot])); mark[tot]=0; } root=trie[root][id]; } mark[root]=true; } void getfail() { memset(f,0,sizeof(f)); for(int i=0;i<63;i++) trie[0][i]=1; q.push(1); int now,j; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<63;i++) { if(!trie[now][i]) { trie[now][i]=trie[f[now]][i]; continue; } q.push(trie[now][i]); j=f[now]; f[trie[now][i]]=trie[j][i]; if(mark[trie[j][i]]) mark[trie[now][i]]=true; } } } double dpp(int now,int L) { if(!L) return 1.0; if(!now) now=1; if(v[now][L]) return dp[now][L]; v[now][L]=true; double ans=0.0; for(int i=1;i<=n;i++) { int id=get(ch[i]); if(!mark[trie[now][id]]) ans+=p[i]*dpp(trie[now][id],L-1); } return dp[now][L]=ans; } int main() { int T; scanf("%d",&T); for(int t=1;t<=T;t++) { scanf("%d",&n); memset(trie[1],0,sizeof(trie[1])); // memset(dp,0,sizeof(dp)); memset(v,0,sizeof(v)); tot=1; while(n--) { scanf("%s",s); insert(); } getfail(); scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>ch[i]; scanf("%lf",&p[i]); } int L; scanf("%d",&L); printf("Case #%d: %.6lf ",t,dpp(1,L)); } }
另一种构造失配指针的写法
2个地方不一样
1、AC自动机从0开始，上面0作为虚拟节点
2、0不能直接入队，枚举0节点的孩子，让孩子入队
因为0的失配指针是0
f[trie[now][i]]=trie[j][i]=trie[0][i]=本节点
导致失配指针指向自己
上面让1入队，1的失配指针是0
void getfail() { memset(f,0,sizeof(f)); for(int i=0;i<63;i++) if(trie[0][i]) q.push(trie[0][i]); int now,j; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<63;i++) { if(!trie[now][i]) { trie[now][i]=trie[f[now]][i]; continue; } q.push(trie[now][i]); j=f[now]; //while(!trie[j][i]) j=f[j]; f[trie[now][i]]=trie[j][i]; if(mark[trie[j][i]]) mark[trie[now][i]]=true; } } }