题意：给你 k 个模板串，然后给你一些字符的出现概率，然后给你一个长度 l ，问你这些字符组成的长度为 l 的字符串不包含任何一个模板串的概率。
思路：AC自动机+概论DP
上次记不得AC自动机怎么写了，今天又写了一波，结果又写GG了，太久没碰字符串了啊；
首先用K个模板构造好AC自动机。题目上说长L的新串的子串不包含任何一个K串，其实就是说在构造好的树中，从根往下走L步都不包含K个模板,遇到ed就停下
#includeusing namespace std;const int ME = 1000;int idc, siz = 63, tot, fail[ME], ch[ME][64];char s[25];bool ed[ME], vis[ME][105];double dp[ME][105], p[100];inline int go(char a){ if(a<='9'&&a>='0')return a-'0'; if(a<='z'&&a>='a')return a-'a'+11; return a-'A'+37;}inline int newnode(){ ++tot; ed[tot] = fail[tot] = 0; memset(ch[tot], 0, sizeof(ch[tot])); return tot;}void insert(char *s){ int now = 0, len = strlen(s); for(int i = 0; i < len; i++){ int t = go(s[i]); if(!ch[now][t])ch[now][t] = newnode(); now = ch[now][t]; } ed[now] = 1;}queue q;void build(){ for(int i = 0; i < siz; i++){ if(ch[0][i])q.push(ch[0][i]); } fail[0] = -1; while(!q.empty()){ int u = q.front();q.pop(); for(int i = 0; i < siz; i++){ if(ch[u][i])q.push(ch[u][i]), fail[ch[u][i]] = ch[fail[u]][i]; else ch[u][i] = ch[fail[u]][i]; } ed[u] |= ed[fail[u]]; }}double dfs(int u, int l){ if(!l)return 1.0; if(vis[u][l])return dp[u][l]; vis[u][l] = 1; double tmp = 0; for(int i = 0; i < siz; i++) if(!ed[ch[u][i]]) tmp += p[i] * dfs(ch[u][i], l-1); return dp[u][l] = tmp;}void init(){ memset(p, 0, sizeof(p)); memset(vis, 0, sizeof(vis)); tot = 0; memset(ch[0], 0, sizeof(ch[0]));}int main(){ int T; scanf("%d", &T); while(T--){ int K, n, l; scanf("%d", &K); init(); for(int i = 1; i <= K; i++){ scanf("%s", s); insert(s); } scanf("%d", &n); char c[2];double oi; for(int i = 1; i <= n; i++){ scanf("%s%lf",c, &oi); p[go(c[0])] = oi; } scanf("%d", &l); build(); double ans = dfs(0, l); printf("Case #%d: %.6lf\n",++idc, ans); }}