UVa 11468 AC自动机+记忆化搜索
题目链接
题意：给你K个模板串(K <= 20， len <= 20)， 再给你n个字符和这些字符各自出现的概率（n个概率之和必为1），然后让你用n个字符来生存长度为L（L <= 100）的串，这个串不能含有n个模板串的任何一个串， 问生成这样一个串的概率为多少。
分析：一看本题数据范围比较小，又涉及概率问题，其中的递推关系也不难找到，所以可用记忆化搜索解决。
思路：用n个模板串构造AC自动机（改造的自动机在本题中比较方便），标记每个单词结尾的节点，表示这些节点不能到达（禁止点）。 记忆化搜索传入 变量u， l，分别表示当前访问的节点编号和生成串还需要构造的长度，然后很容易根据递归写出来。
注意： 禁止点不仅仅是每个单词结尾的节点， 如 abcd，bc， 这时，abcd 中的c也是禁止点，所以在生成失配函数的适合我们要更新这些点，我们发现禁止点转移的方向跟失配后转移的方向正好相反， 如果我们要更新节点v，我们可以用f[v]去更新它。
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <queue>#include <cctype>using namespace std;const int maxn = 22 * 22;int n;char s[22], str[maxn][3];double p[maxn];struct AC {int val[maxn], c[maxn][77], tot, f[maxn];int idx(char c) { return islower(c) ? c-'a' : isupper(c) ? c-'A'+26 : c-'0'+52; }int new_node() { memset(c[tot], 0, sizeof(c[tot]));val[tot] = 0;return tot++;}void init() { tot = 0; new_node(); }void insert(char *s) {int i, j, u = 0, n = strlen(s);for(i = 0; i < n; i++) {int k = idx(s[i]);if(!c[u][k]) c[u][k] = new_node();u = c[u][k];}val[u] = 1;}void getfail() {int i, j, u, v;queue <int> q;f[0] = 0;for(i = 0; i < 62; i++) {u = c[0][i];if(u) { f[u] = 0; q.push(u); }}while(!q.empty()) {u = q.front(); q.pop();for(i = 0; i < 62; i++) {v = c[u][i];if(!v) { c[u][i] = c[f[u]][i]; continue; }j = f[u];while(j && !c[j][i]) j = f[j];f[v] = c[j][i];q.push(v);val[v] |= val[f[v]]; // 注意， abcd, bc}}}bool vis[maxn][103];double dp[maxn][103];double gao(int u, int l) {if(!l) return 1.0;if(vis[u][l]) return dp[u][l];vis[u][l] = 1;double &ret = dp[u][l];ret = 0.0;int i, j;for(i = 0; i < n; i++) {int k = idx(str[i][0]);if(!val[c[u][k]])ret += p[i] * gao(c[u][k], l-1);}return ret;}}ac;int main() {int i, j, cas, l;scanf("%d", &cas);for(int ca = 1; ca <= cas; ca++) {ac.init();scanf("%d", &n);while(n--) {scanf("%s", s);ac.insert(s);}ac.getfail();scanf("%d", &n);for(i = 0; i < n; i++)scanf("%s%lf", str[i], &p[i]);memset(ac.vis, 0, sizeof(ac.vis));scanf("%d", &l);printf("Case #%d: %.6lf\n", ca, ac.gao(0, l) );}return 0;}