UVA 11468【AC自动机+DP】

时间:2021-05-10 16:06:20

dp[i][j]表示走了i步走到j结点的概率。初始值dp[0][0] = 1.当走到的结点不是单词尾结点时,才能走过去。

!end[i]&&last[i] == root时,该结点才可行。

丢掉last数组, end[i] |= end[ fail[i] ]即可。 表示i节点是某些禁止字符串的后缀。

 #include <bits/stdc++.h>
using namespace std;
const int N = ;
int id(char c){
if(c >= ''&&c <= '') return c-'';
if(c >= 'a'&&c <= 'z') return c-'a'+;
if(c >= 'A'&&c <= 'Z') return c-'A'+;
return -;
}
struct Tire{
int nex[N][], fail[N], end[N];
int root, L;
int newnode(){
memset(nex[L], -, sizeof(nex[L]));
end[L] = ;
return L++;
}
void init(){
L = ;
root = newnode();
}
void insert(char* s){
int now = root;
for(int i = ; s[i]; i++){
int p = id(s[i]);
if(nex[now][p] == -)
nex[now][p] = newnode();
now = nex[now][p];
}
end[now] = ;
}
void build(){
queue<int> Q;
fail[root] = root;
for(int i = ; i < ; i++){
int& u = nex[root][i];
if(u == -)
u = root;
else{
fail[u] = root;
Q.push(u);
}
}
while(!Q.empty()){
int now = Q.front();
Q.pop();
for(int i = ; i < ; i++){
int& u = nex[now][i];
if(u == -)
u = nex[ fail[now] ][i];
else{
fail[u] = nex[ fail[now] ][i];
end[u] |= end[ fail[u] ];
//last[u] = end[ fail[u] ]? fail[u] : last[ fail[u] ];
Q.push(u);
}
}
}
}
};
Tire ac;
double por[];
char s[];
double dp[][N];
int main(){
int n, k, t, ca = ; scanf("%d", &t);
while(t--){
ac.init();
scanf("%d", &k);
for(int i = ; i < k; i++){
scanf("%s", s);
ac.insert(s);
}
ac.build();
memset(por, , sizeof(por));
scanf("%d", &n);
char ch;
for(int i = ; i < n; i++){
scanf(" %c", &ch);
int p = id(ch);
scanf("%lf", por+p);
}
int l; scanf("%d", &l);
memset(dp, , sizeof(dp));
dp[][] = ;
for(int i = ; i < l; i++){
for(int j = ; j < ac.L; j++)
if(dp[i][j] > ) for(int k = ; k < ; k++){
int ret = ac.nex[j][k];
if(!ac.end[ret])
dp[i+][ret] += dp[i][j]*por[k];
}
}
double ans = ;
for(int i = ; i < ac.L; i++)
ans += dp[l][i];
printf("Case #%d: %f\n", ca++, ans);
}
return ;
}