[JSOI2007]文本生成器（AC自动机+DP）

题意

给你n个串。问有多少长度为m的串使得这n个串至少在其中出现过一次。输出答案膜10007意义下的结果。

（n<=100,每个串的长度<=100）

题解

在AC自动机上跑DP。

用到一个容斥的思想，求至少出现过一次的次数就是，全部可能-一次都没出现的次数。

所以考虑dp，对于一个长度为i的串从i-1转移，i位置上的数必须不是n个串中某个串的结尾。

所以建立AC自动机，在上面跑。一个儿子从父亲转移时必须保证，儿子节点和儿子节点通过fail指针间接到达的点，都不是终止节点。

具体看代码。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int mod=;

 const int N=;

 int n,m,tot,ans;

 char s[N];

 int dp[][N];

 struct AC{

     int nxt[],e,fail;

 }ac[N];

 void insert(char s[]){

 //    cout<<"asfsfsdfsdfs"<<endl;

     int len=strlen(s);

     int now=;

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

         if(ac[now].nxt[s[i]-'A']==)ac[now].nxt[s[i]-'A']=++tot;

         now=ac[now].nxt[s[i]-'A'];

     }

     ac[now].e=;

 }

 void get_fail(){

     queue<int>q;

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

         if(ac[].nxt[i]){

         //    cout<<"sfsd"<<endl;

             q.push(ac[].nxt[i]);

         }

     }

     while(!q.empty()){

         int u=q.front();//cout<<u<<endl;

         q.pop();

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

             if(ac[u].nxt[i]){

                 ac[ac[u].nxt[i]].fail=ac[ac[u].fail].nxt[i];

                 ac[ac[u].nxt[i]].e|=ac[ac[ac[u].fail].nxt[i]].e;

                 q.push(ac[u].nxt[i]);

             }

             else ac[u].nxt[i]=ac[ac[u].fail].nxt[i];

         }

     }

 }

 int main(){

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

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

         scanf("%s",s);

         insert(s);

     }

     get_fail();

     dp[][]=;

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

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

             for(int x=;x<=;x++){

                 if(ac[ac[j].nxt[x]].e==)dp[i][ac[j].nxt[x]]=(dp[i][ac[j].nxt[x]]+dp[i-][j])%mod;

             }

     int ans=;

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

         ans*=;

         ans%=mod;

     }

     for(int i=;i<=tot;i++){

         ans-=dp[m][i];

         ans=(ans+mod)%mod;

     }

     printf("%d",ans);

     return ;

 }

巴特西

[JSOI2007]文本生成器（AC自动机+DP）

题意

题解

最新文章

热门文章