分析

仍然考虑 。我们考虑这个串是否可行，主要看是否经过了一个 的节点。那么我们定义 表示考虑前 长的串，现在到了 节点，合法，不合法的个数分别有多少个。那么转移就暴力转移了，因为 和 都很小。那么总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 100,mod = 1e4 + 7;
int f[110][N][2],fail[N],ch[N][26],val[N],size;
int n,m;
void insert(char *S) {
    int len = strlen(S + 1),u = 0;
    for(int i = 1;i <= len;i++) {
        int c = (S[i] - 'A');
        if(!ch[u][c]) ch[u][c] = ++size;
        u = ch[u][c];
    }val[u] |= 1;
}
void build() {
    queue<int> Q;
    for(int i = 0;i < 26;i++) if(ch[0][i]) Q.push(ch[0][i]);
    while(!Q.empty()) {
        int x = Q.front();Q.pop();
        for(int i = 0;i < 26;i++) {
            int y = ch[x][i];
            if(y) {fail[ch[x][i]] = ch[fail[x]][i];val[y] |= val[fail[y]];Q.push(y);}
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}
void inc(int &x,int y) {x = (x + y) % mod;}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) {
        static char S[N];scanf("%s",S + 1);insert(S);
    }
    build();
    f[0][0][0] = 1;
    for(int i = 0;i < m;i++) {
        for(int j = 0;j <= size;j++) {
            if(val[j]) inc(f[i][j][1],f[i][j][0]),f[i][j][0] = 0; 
            for(int k = 0;k < 26;k++) {
                inc(f[i + 1][ch[j][k]][0],f[i][j][0]);
                inc(f[i + 1][ch[j][k]][1],f[i][j][1]);
            }
        }
    }
    int ans = 0;
    for(int i = 0;i <= size;i++) {
        if(val[i]) inc(f[m][i][1],f[m][i][0]),f[m][i][0] = 0;
        inc(ans,f[m][i][1]);
    }
    cout << ans << endl;return 0;
}