首先我们应该是枚举 L个位置上的每个字符来得到最终概率
然后AC自动机的作用就是为了判断你枚举的地方是否对应了单词节点，如果对应了，就肯定要不得
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int max_node = 500; const int N =256; const int node_num=64; int idx[N],k,n; char str[30][30]; double prob[100]; //这个地方一开始开小了，题目也没说n为多少。坑啊。。一直RE没找到原因 int vis[max_node][110]; double d[max_node][110]; struct ACtrie { int ch[max_node][64]; int sz; int val[max_node]; int fail[max_node]; //int last[max_node]; void init(){ memset(ch,0,sizeof ch); memset(val,0,sizeof val); memset(fail,0,sizeof fail); //memset(last,0,sizeof last); sz=1; } void insert(char* s,int v){ int u=0; for (int i=0;s[i];i++){ int c=idx[s[i]]; if (!ch[u][c]){ memset(ch[sz],0,sizeof ch[sz]); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=1; } void getfail(){ queue<int> q; fail[0]=0; for (int i=0;i<node_num;i++) if (ch[0][i]){ fail[ch[0][i]]=0; q.push(ch[0][i]); } while (!q.empty()){ int u=q.front(); q.pop(); for (int c=0;c<node_num;c++){ int v=ch[u][c]; if (!v) {ch[u][c] = ch[fail[u]][c];continue;} //这个个普通AC自动机不一样，因为要一视同仁所有字符，当前字符在该子树如果找不到就可以转到其失败节点去，因为失败节点有的话，同样是满足条件的 q.push(v); int p=fail[u]; while (p && !ch[p][c]) p=fail[p]; fail[v]=ch[p][c]; //last[v]=val[fail[p]]?fail[p] : last[fail[p]]; val[v]|=val[fail[v]]; } } } } T; double getprob(int u,int L) { if (L==0) return 1.0; if (vis[u][L]) return d[u][L]; vis[u][L]=1; d[u][L]=0.0; for (int i=0;i<n;i++){ if (!T.val[T.ch[u][i]]) d[u][L]+=prob[i]*getprob(T.ch[u][i],L-1); } return d[u][L]; } int main() { int t,L; char cc[9]; scanf("%d",&t); int kase=0; while (t--){ T.init(); scanf("%d",&k); for (int i=0;i<k;i++) scanf("%s",str[i]); scanf("%d",&n); for (int i=0;i<n;i++){ scanf("%s%lf",&cc,&prob[i]); idx[cc[0]]=i; } for (int i=0;i<k;i++){ T.insert(str[i],1); } T.getfail(); memset(vis,0,sizeof vis); scanf("%d",&L); double ans=getprob(0,L); printf("Case #%d: %.6lf ",++kase,ans); } return 0; }