比较容易看出来先建立ac自动机，然后在自动机上做DP，设w[0..1][i][j]为当前不包括/包括字典中的字符串，当前在自动机中走到第i个节点，完成的文本的长度为j的方案数，那么比较容易的转移w[i|j->child->cnt][j->child][k+1]+=w[i][j][k]。

　　

/**************************************************************    Problem: 1030    User: BLADEVIL    Language: C++    Result: Accepted    Time:200 ms    Memory:25596 kb****************************************************************/ //By BLADEVIL#include 
     
      #include 
      
       #define maxn 10010#define maxm 200#define d39 10007 using namespace std; int n,m;int w[3][maxm][maxn]; struct node{    int cnt,num;    node *child[30],*fail;    node (){        cnt=num=0;        memset(child,0,sizeof child);        fail=NULL;    }} nodepool[maxn],*totnode,*root,*que[maxn]; void build_trie(){    totnode=nodepool; root=totnode++;    for (int i=1;i<=n;i++){        char c[maxm];        scanf("%s",&c);        int len=strlen(c);        node *t=root;        for (int j=0;j
       
        child[c[j]-'A']) t->child[c[j]-'A']=totnode++;            t=t->child[c[j]-'A'];        }        t->cnt=1;    }} void build_ac(){    int h=0,t=1;    que[1]=root; root->fail=root;     for (int i=0;i<26;i++) if (!root->child[i])   root->child[i]=root;    while (h
        
         child[i]&&u->child[i]!=root){            que[++t]=u->child[i];            que[t]->fail=u->fail->child[i]!=que[t]?u->fail->child[i]:root;            que[t]->cnt|=que[t]->fail->cnt;        } else u->child[i]=u->fail->child[i];    }} void dp(){    int j=1;    for (node *i=nodepool;i!=totnode;i++) i->num=j++;//for (node *i=nodepool;i!=totnode;i++) printf("%d %d %d\n",i->cnt,i->num,i->fail->num);    w[0][1][1]=1;    for (int t=0;t<2;t++)        for (int i=1;i<=m;i++)            for (node *j=nodepool;j!=totnode;j++)                if (w[t][i][j->num])                    for (int k=0;k<26;k++)                        (w[t|j->child[k]->cnt][i+1][j->child[k]->num]+=w[t][i][j->num])%=d39;    int ans=0;    for (node *i=nodepool;i!=totnode;i++)        (ans+=w[1][m+1][i->num])%=d39;    printf("%d\n",ans);} int main(){    scanf("%d%d",&n,&m);    build_trie();    build_ac();    dp();    return 0;}