AC自己主动机的题，须要注意的，建立失配边的时候，假设结点1失配边连到的那个结点2，那个结点2是一个单词的结尾，那么这个结点1也须要标记成1（由于能够看成，这个结点包括了这个单词），之后在Trie树上进行行走，每次走到下一个能够走的结点。
| 14378527 | 11468 | Substring | Accepted | C++ | 0.585 | 2014-10-19 10:35:00 |
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 444;
const int max_size = 66;
const int maxd = 111;
int M,Case = 1;
int ch[max_size];
double P[max_size];
int index(int c){
if(c >= 'A' && c <= 'Z') return c - 'A';
if(c >= 'a' && c <= 'z') return c - 'a' + 26;
if(c >= '0' && c <= '9') return c - '0' + 52;
}
struct Trie{
int next[maxn][max_size];
int fail[maxn];
int val[maxn];
int vis[maxn][maxd];
double dp[maxn][maxd];
int sz,root;
int newnode(){
val[sz] = 0;
memset(next[sz],-1,sizeof(next[sz]));
sz ++;
return sz - 1;
}
void init(){
sz = 0;
root = newnode();
memset(vis,0,sizeof(vis));
return;
}
void insert(char *str){
int now = root;
int L = strlen(str);
for(int i = 0; i < L; i++){
int e = index(str[i]);
if(next[now][e] == -1)
next[now][e] = newnode();
now = next[now][e];
}
val[now] = 1;
return;
}
void build(){
queue<int>q;
fail[root] = root;
for(int i = 0; i < max_size ; i++)
if(next[root][i] != -1){
fail[next[root][i]] = root;
q.push(next[root][i]);
}
else
next[root][i] = root;
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = 0; i < max_size ; i++){
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else{
q.push(next[now][i]);
fail[next[now][i]] = next[fail[now]][i];
val[next[now][i]] |= val[fail[next[now][i]]];
}
}
}
return;
}
double DP(int pos,int L){
if(!L) return 1.0;
if(vis[pos][L])
return dp[pos][L];
vis[pos][L] = 1;
double &ans = dp[pos][L];
ans = 0.0;
for(int i = 0; i < M; i++){
int e = ch[i];
if(!val[next[pos][e]])
ans += P[i] * DP(next[pos][e],L - 1);
}
return ans;
}
}ac;
int main(){
int T;
scanf("%d",&T);
while(T--){
ac.init();
int K;
scanf("%d",&K);
for(int i = 0; i < K; i++){
char str[maxn];
scanf("%s",str);
ac.insert(str);
}
ac.build();
scanf("%d",&M);
for(int i = 0; i < M; i++){
char str[maxn];
scanf("%s%lf",str,&P[i]);
ch[i] = index(str[0]);
}
int L;
scanf("%d",&L);
double ans = ac.DP(0,L);
printf("Case #%d: %.6f
",Case++,ans);
}
return 0;
}