UVa 11468 Substring AC自动机+概率DP

题目来源：UVA 11468 Substring

题意：求不包含任意一个模式串的长度为l的文本串的概率 给出可以使用的字符的种类及其概率

思路：AC自动机+概率DP

 

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxnode = 20*22;
const int size = 66;
int ch[maxnode][size];
int val[maxnode];
int f[maxnode];
int sz;

int id[size];
double pro[size];
char str[22][22];
bool vis[maxnode][110];
double dp[maxnode][110];
int m;

int idx(char c)
{
if(c >= 'a' && c <= 'z')
return c - 'a';
if(c >= 'A' && c <= 'Z')
return c - 'A' + 26;
return c - '0' + 52;
}
void init()
{
sz = 1;
memset(ch[0], 0, sizeof(ch[0]));
}
void insert(char *s, int v)
{
int u = 0, n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = id[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;
f[0] = 0;
val[0] = 0;
for(int c = 0; c < m; c++)
{
int u = ch[0][c];
if(u)
{
f[u] = 0;
q.push(u);
}
}
while(!q.empty())
{
int r = q.front(); q.pop();

for(int c = 0; c < m; c++)
{
int u = ch[r][c];
if(!u)
{
ch[r][c] = ch[f[r]][c];
continue;
}
q.push(u);
int v = f[r];
while(v && !ch[v][c])
v = f[v];
f[u] = ch[v][c];
val[u] |= val[f[u]];
}
}
}

double dfs(int u, int l)
{
if(!l)
return 1.0;
if(vis[u][l])
return dp[u][l];
vis[u][l] = true;
dp[u][l] = 0.0;
for(int i = 0; i < m; i++)
{
if(!val[ch[u][i]])
dp[u][l] += pro[i] * dfs(ch[u][i], l-1);
}
return dp[u][l];

}
int main()
{
int cas = 1;
int T;
scanf("%d", &T);
while(T--)
{
init();
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%s", str[i]);
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
char s[5];
scanf("%s %lf", s, &pro[i]);
int c = idx(s[0]);
id[c] = i;
}
for(int i = 0; i < n; i++)
insert(str[i], i);
getFail();
int l;
scanf("%d", &l);
memset(vis, false, sizeof(vis));
printf("Case #%d: %.6f\n", cas++, dfs(0, l));
}
return 0;
}