答案=方案总数-不合法总数； 设AC自动机上非法节点为终止节点（或fail指针指向终止节点的点） dp[ i ] [ j ]为当前在AC自动机上跑了 i 步 ，跑到 j 节点的方案数，其中过程不经过非法节点。 不合法方案数=sigma（dp[ m ] [ i ]）其中 i 不是为合法节点。
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #define maxn 100005 #define LL long long using namespace std; int m,mod=10007; char s[maxn]; int dp[105][10005]; LL pow(LL x,int y) { if(y==1) return x; LL a=pow(x,y/2); a=(a*a)%mod; if(y%2) return (a*x)%mod; return a; } struct Trie { bool no[maxn]; int val[maxn]; int ch[maxn][30],cnt; int lst[maxn],fail[maxn]; void insert() { int p=0; int n=strlen(s+1); for(int i=1;i<=n;i++) { int c=s[i]-'A'+1; if(!ch[p][c]) ch[p][c]=++cnt; p=ch[p][c]; } no[p]=1; } queue<int> Q; void build() { for(int i=1;i<=26;i++) if(ch[0][i]) Q.push(ch[0][i]); while(!Q.empty()) { int r=Q.front();Q.pop(); for(int i=1;i<=26;i++) { int u=ch[r][i]; if(!u) { ch[r][i]=ch[fail[r]][i]; continue; } Q.push(u); int p=fail[r]; while(p&&!ch[p][i]) p=fail[p]; fail[u]=ch[p][i]; no[u]|=no[fail[u]]; } } } int work() { int ans=pow(26,m); dp[0][0]=1; for(int i=1;i<=m;i++) for(int j=0;j<=cnt;j++) { if(no[j]||dp[i-1][j]==0)continue; for(int k=1;k<=26;k++) { dp[i][ch[j][k]]+=dp[i-1][j]; dp[i][ch[j][k]]%=mod; } } for(int i=0;i<=cnt;i++) if(!no[i]) ans-=dp[m][i]; while(ans<0) ans+=mod; ans%=mod; return ans; } }AC; int main() { int n; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",s+1); AC.insert(); } AC.build(); printf("%d",AC.work()); return 0; }