UVA 11468
dp[i][l]表示在结点i再走l步不碰到单词结点的概率。
关键一步：val[u]|=val[fail[u]];
#include<iostream> #include<vector> #include<queue> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; const int MAX_NODE=444; const int SIGMA_SIZE=62; struct ACAutomation { int sz; int fail[MAX_NODE]; int ch[MAX_NODE][SIGMA_SIZE]; int val[MAX_NODE]; double dp[444][200]; int idx(char c) { if(c>='0'&&c<='9')return c-'0'; if(c>='A'&&c<='Z')return c-'A'+10; if(c>='a'&&c<='z')return c-'a'+36; } void init() { sz=1; memset(ch[0],0,sizeof(ch[0])); val[0]=0; memset(dp,-1,sizeof(dp)); } void insert(const char *s) { int u=0; for(int i=0; s[i]!='