摘要：
乍一看，似乎没有办法转移这个问题，但这只是将两个知识点挤在一起的问题。要判断多个字符串是否是一个字符串的子字符串，首先考虑AC自动机：将模板字符串构建为AC自动机，然后对其进行dp。AC自动机上从每个节点到根的路径表示前缀，因此模板字符串可以匹配节点，文本字符串可以匹配长度。然后很容易想到转移：。
传送
这题乍一看觉得无从下手，但只不过是把两个知识点捏到一块罢了。
判断多个串是否为一个串的子串，首先想到AC自动机：把(K)个模板串建成AC自动机，然后在上面dp（记忆化搜索）。
AC自动机上的每一个节点到根的路径都代表一个前缀，所以令(dp[i][j])表示模板串匹配到节点(i)，文本串匹配到长度(j)时的"no"可能性。
那么转移就很好想了：(dp[u][j] = sum_{c in 字符集} p[c] * dp[v][j+1])。只要不往模板串代表的节点转移即可。
需要注意的是，如果一个节点为一个模板串的结束位置，那么他在fail树上的所有后代节点都是该模板串的结束位置，所以构造fail指针的时候要(num[u] |= num[v])（(v)是(u)的后代）。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const db eps = 1e-8;
const int maxt = 70;
const int maxN = 4e4 + 5;
const int maxn = 105;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, L;
char s[maxn];
db p[maxt];
int ch[maxN][maxt], f[maxN], num[maxN], cnt = 0;
In void Clear(int x) {Mem(ch[x], 0), f[x] = num[x] = 0;}
In int C(char c)
{
if(isdigit(c)) return c - '0';
else if(islower(c)) return c - 'a' + 11;
else return c - 'A' + 37;
}
In void insert(char* s)
{
int m = strlen(s), now = 0;
for(int i = 0; i < m; ++i)
{
int c = C(s[i]);
if(!ch[now][c]) Clear(++cnt), ch[now][c] = cnt;
now = ch[now][c];
}
num[now] = 1;
}
In void build()
{
queue<int> q;
for(int i = 0; i < maxt; ++i) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = 0; i < maxt; ++i)
if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]);
else ch[now][i] = ch[f[now]][i];
num[now] |= num[f[now]];
}
}
bool vis[maxN][maxn];
db dp[maxN][maxn];
In db dfs(int now, int len) //记忆化搜索
{
if(len == L + 1) return 1;
if(vis[now][len]) return dp[now][len];
vis[now][len] = 1; db ret = 0;
for(int i = 0; i < maxt; ++i)
if(!num[ch[now][i]]) ret += p[i] * dfs(ch[now][i], len + 1);
return dp[now][len] = ret;
}
In void init()
{
Mem(p, 0), Mem(vis, 0), Mem(dp, 0);
Clear(cnt = 0);
}
int main()
{
int T = read();
for(int id = 1; id <= T; ++id)
{
init();
n = read();
for(int i = 1; i <= n; ++i)
{
scanf("%s", s);
insert(s);
}
build();
m = read();
for(int i = 1; i <= m; ++i)
{
char cc[2]; db tp;
scanf("%s%lf", cc, &tp);
p[C(cc[0])] = tp;
}
L = read();
printf("Case #%d: %.6lf
", id, dfs(0, 1));
}
return 0;
}