也是挺基础的 ACAM 上 dp。
设 \(dp_{i,j,k}\) 表示当前长度在 \(i\)，在 ACAM 上的节点 \(j\)，有没有字典中的单词 的计数结果。
那么直接在 ACAM 上跑就行了。
复杂度 \(\mathrm{O}(m \Sigma |s_i| |\Sigma|)\)，其中 \(|\Sigma|\) 为字符集大小。
#include <bits/stdc++.h>
#define llong long long
#define N 10004
#define M 105
using namespace std;constexpr int p = 1e4+7;
char a[N];
int son[N][32], tag[N], fail[N], tsiz = 1;
int dp[M][N][2];
int n, m, ans;int que[N], he, ta;int main(){scanf("%d %d", &n, &m);for(int i = 1, l; i <= n; ++i){scanf("%s", a+1), l = strlen(a+1);int x = 1;for(int j = 1; j <= l; ++j){if(!son[x][a[j]^64]) son[x][a[j]^64] = ++tsiz;x = son[x][a[j]^64];}tag[x] = true;}he = 1, ta = 0;for(int i = 1; i <= 26; ++i){if(son[1][i]) fail[son[1][i]] = 1, que[++ta] = son[1][i];else son[1][i] = 1;}while(he <= ta){int x = que[he++];tag[x] |= tag[fail[x]];for(int i = 1; i <= 26; ++i){if(son[x][i]) fail[son[x][i]] = son[fail[x]][i], que[++ta] = son[x][i];else son[x][i] = son[fail[x]][i];}}dp[0][1][0] = 1;for(int i = 0; i < m; ++i)for(int j = 1; j <= tsiz; ++j)for(int k = 1; k <= 26; ++k)for(int l = 0; l <= 1; ++l)dp[i+1][son[j][k]][l|tag[son[j][k]]] = (dp[i+1][son[j][k]][l|tag[son[j][k]]]+dp[i][j][l])%p;for(int i = 1; i <= tsiz; ++i)ans = (ans+dp[m][i][1])%p;printf("%d", ans);return 0;
}``