正难则反，我们发现用总字符串个数\(26^m\)，减去不可读的字符串个数，就是答案。
要使一个字符串不可读，就不能让任何模式串在其中出现。如果某个主串的第\(i\)位与自动机的节点\(j\)相匹配，那么如果状态\(j\)包含模式串（即有一个前缀是一个模式串），那么不管主串第\(i+1\)位后是什么，一定是不可读的，故此时“主串第\(i\)个字符，对应节点\(j\)”的答案是\(0\)。
再考虑\(j\)不包含任何模式串的情况，显然我们就可以把“主串第\(i-1\)个字符，对应节点\(fa[j]\)”的答案，转移到“主串第\(i\)个字符，对应节点\(j\)”上去。
其中\(fa[j]\)表示在Trie图上能通过一条有向边到达\(j\)的节点，可能有多个。
因此我们用\(f[i][j]\)表示主串第\(i\)个字符，对应节点\(j\)的答案，可以得到转移：
f[0][0]=1;
for(int i=1;i<=m;i++)//枚举长度
for(int j=0;j<=cnt;j++)//枚举所有Trie节点
for(int c=0;c<26;c++)
if(!fl[tr[j][c]])//如果tr[j][c]不包含模式串
f[i][tr[j][c]]+=f[i-1][j];//j转移到tr[j][c]
最后就是如何计算\(fl\)数组，即判断某个节点是否包含模式串。这个显然能在get_fail()中一并处理出来。如果\(u\)是模式串结尾，或者\(fl[fail[u]]=1\)，那么\(fl[u]=1\)。
时间复杂度是\(O(m\times \sum|s|\times |\Sigma|)\)，其中建自动机是\(O(\sum|s|\times |\Sigma|)\)。
别忘了取模~
点击查看代码
#include<bits/stdc++.h>
#define mod 10007
#define N 6010//节点数（模式串总长）
#define M 110//单个模式串长度
#define C 26//字符集大小
using namespace std;
int n,m,tr[N][C],fail[N],cnt;
int q[N],head,tail,f[M][N],fa[N];
bool fl[N];
string s;
void ins(string s){
int p=0;
for(char i:s){
int c=i-'A';
if(!tr[p][c]) tr[p][c]=++cnt,fa[cnt]=p;
p=tr[p][c];
}
fl[p]=1;
}
void get_fail(){
head=0,tail=-1;
for(int i=0;i<26;i++) if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<26;i++){
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q[++tail]=tr[u][i],
fl[tr[u][i]]|=fl[fail[tr[u][i]]];
else tr[u][i]=tr[fail[u]][i];
}
}
}
int qpow(int a,int b){
int fac=1;
while(b){
if(b&1) fac=fac*a%mod;
a=a*a%mod,b>>=1;
}
return fac;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s;
ins(s);
}
get_fail();
int ans=0;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=cnt;j++)
for(int c=0;c<26;c++)
if(!fl[tr[j][c]])
f[i][tr[j][c]]=(f[i][tr[j][c]]+f[i-1][j])%mod;
for(int i=0;i<=cnt;i++) ans=(ans+f[m][i])%mod;
ans=(qpow(26,m)-ans+mod)%mod;
cout<<ans<<"\n";
return 0;
}