文本生成器(AC自动机上DP)

#include<bits/stdc++.h>
using namespace std;
const int L = 105;
const int mod = 1e4 + 7;
int n, m, cnt, ans = 1, tr[L * 60][30], fail[L * 60], dp[L][L * 60], flag[L * 60];
char s[L];
vector<int> mp[L * 60];
void build(char *s){int p = 0;for(int i = 0, len = strlen(s); i < len; i++){if(!tr[p][s[i] - 'A']) tr[p][s[i] - 'A'] = ++cnt;p = tr[p][s[i] - 'A'];}flag[p] |= 1;
}
void ac(){queue<int> q;for(int i = 0; i < 26; i++){if(!tr[0][i]) continue;fail[tr[0][i]] = 0;q.push(tr[0][i]);}while(!q.empty()){int u = q.front(); q.pop();for(int i = 0; i < 26; i++){if(tr[u][i]){fail[tr[u][i]] = tr[fail[u]][i];flag[tr[u][i]] |= flag[tr[fail[u]][i]];q.push(tr[u][i]);}else tr[u][i] = tr[fail[u]][i];}}
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s;build(s);}ac();dp[0][0] = 1;for(int i = 1; i <= m; i++){for(int j = 0; j < 26; j++){for(int k = 0; k <= cnt; k++){if(!flag[tr[k][j]]) dp[i][tr[k][j]] = (dp[i][tr[k][j]] + dp[i - 1][k]) % mod;}}}int sum = 0;for(int i = 0; i <= cnt; i++) sum = (sum + dp[m][i]) % mod;for(int i = 1; i <= m; i++) ans = (ans * 26) % mod;cout << (ans - sum + mod) % mod;return 0;
}