【Trie图+DP】BZOJ1030[JSOI2007]-文本生成器

【题目大意】

给出单词总数和固定的文章长度M，求出至少包含其中一个单词的可能文章数量。

【思路】

对于至少包含一个的类型，我们可以考虑补集。也就是等于[总的文章可能性总数-不包含任意一个单词的文章总数]有两个注意点：

1.Trie图+DP。Trie图和AC自动机的区别在于，当孩子i为NULL时，则让孩子指针等于fail指针的孩子i，这样就可以继续匹配下去了。因此寻找fail指针的时候，可以不用循环而用判断语句即可。

2.danger表示当前位置包含了单词，所以DP的时候舍去。如果你指向的fail指针是danger的，也就是你的后缀是danger的，那么当前的也是danger的。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int MAXN=+;

 const int MAXM=+;

 const int MOD=;

 const int NUMA=;

 int n,m,cnt=;

 struct ACauto

 {

     int id;

     int danger;

     ACauto* next[NUMA];

     ACauto* fail;

     ACauto()

     {

         danger=;

         id=++cnt;

         for (int i=;i<NUMA;i++) next[i]=NULL;

         fail=NULL;

     }

 };

 ACauto* node[MAXN*MAXM];

 int f[MAXN][MAXM*MAXN];

 void insert(ACauto* root,char* str)

 {

     int len=strlen(str);

     ACauto* tmp=root;

     for (int i=;i<len;i++)

     {

         int index=str[i]-'A';

         if (tmp->next[index]==NULL)

         {

             tmp->next[index]=new ACauto;

             node[cnt]=tmp->next[index];

         }

         tmp=tmp->next[index];

     }

     tmp->danger=;

 }

 void build(ACauto* root)

 {

     queue<ACauto*> que;

     que.push(root);

     while (!que.empty())

     {

         ACauto* head=que.front();que.pop();

         for (int i=;i<NUMA;i++)

         {

             if (head->next[i]==NULL)

             {

                 if (head==root) head->next[i]=root;

                     else head->next[i]=head->fail->next[i];

             }

             else

             {

                 if (head==root) head->next[i]->fail=root;

                     else

                     {

                         head->next[i]->fail=head->fail->next[i];

                         if (head->next[i]->fail->danger) head->next[i]->danger=;/*注意！*/

                     }

                 que.push(head->next[i]);

             }

         }

     }

 }

 void dp(ACauto* root)

 {

     memset(f,,sizeof(f));

     f[][]=;

     for (int i=;i<=m-;i++)

         for (int j=;j<=cnt;j++)

         {

             if (!node[j]->danger && f[i][j])

             {

                 for (int k=;k<NUMA;k++)//枚举下一个字母

                     if (!node[j]->next[k]->danger)

                         f[i+][node[j]->next[k]->id]=(f[i][j]+f[i+][node[j]->next[k]->id])%MOD;

             }

         }

 }

 void findres()

 {

     int ans1=,ans2=;

     for (int i=;i<=cnt;i++)

         if (!node[i]->danger) ans1=(ans1+f[m][i])%MOD;

     for (int i=;i<=m;i++) ans2=(ans2*NUMA)%MOD;

     cout<<(ans2-ans1+MOD)%MOD<<endl;

 }

 int main()

 {

     char str[MAXN];

     ACauto* root=new ACauto;

     node[]=root;

     scanf("%d%d",&n,&m);

     for (int i=;i<n;i++)

     {

         scanf("%s",str);

         insert(root,str);

     }

     build(root);

     dp(root);

     findres();

     return ;

 }