Uva 11468 Substring——AC自动机+概率DP

Uva 11468 Substring——AC自动机+概率DP

蓝书例题， 蓝书讲的挺明白的

#include #include #include #include #include #include using namespace std;char str[110], c[10];int T, N, M, L, vis[1010][110];double pro[110], p, dp[1010][110];struct AC { int total, match[1010], fail[1010], child[1010][110]; void init() { total = 1; memset(match, 0, sizeof(match)); memset(fail, 0, sizeof(fail)); memset(child[0], 0, sizeof(child[0])); } void Insert(char *P) { int root = 0; for (int i = 0; P[i]; i++) { if (!child[root][P[i] - '0']) { memset(child[total], 0, sizeof(child[total])); child[root][P[i] - '0'] = total++; } root = child[root][P[i] - '0']; } match[root] = 1; } void Getfail() { queue q; for (int i = 0; i < 100; i++) { if (child[0][i]) q.push(child[0][i]); } while (!q.empty()) { int root = q.front(); q.pop(); for (int i = 0; i < 100; i++) { int u = child[root][i]; if (!u) { child[root][i] = child[fail[root]][i]; continue; } q.push(u); int v = fail[root]; while (v && !child[v][i]) v = fail[v]; fail[u] = child[v][i]; match[u] |= match[fail[u]]; } } }}ac;double dfs(int u, int len) { if (!len) return 1.0; if (vis[u][len]) return dp[u][len]; vis[u][len] = 1; double ans = 0; for (int i = 0; i < 100; i++) { if (pro[i] && !ac.match[ac.child[u][i]]) { ans += pro[i] * dfs(ac.child[u][i], len - 1); } } return dp[u][len] = ans;}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { ac.init(); memset(vis, 0, sizeof(vis)); memset(pro, 0, sizeof(pro)); memset(dp, -1, sizeof(dp)); scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%s", str); ac.Insert(str); } ac.Getfail(); scanf("%d", &M); for (int i = 1; i <= M; i++) { scanf("%s %lf", c, &p); pro[c[0] - '0'] = p; } scanf("%d", &L); printf("Case #%d: %lf\n", kase, dfs(0, L)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。