UVALive - 4126 Password Suspects (AC自动机+状压dp)

给你m个字符串，让你构造一个字符串，包含所有的m个子串，问有多少种构造方法。如果答案不超过42，则按字典序输出所有可行解。

由于m很小，所以可以考虑状压。

首先对全部m个子串构造出AC自动机，每个节点有一个附加属性val[u]代表结点u包含的子串集合。

设dp[l][S][u]为长度为l，包含子串集合为S，当前在结点u时，接下来能构造出的合法字符串总数，则dp[l][S][u]=∑dp[l+1][S|val[v]][v],v=go[u][i],0<=i<26;

两遍dfs，一遍dp，一遍输出答案即可。

注意一个结点可能是多个字符串的结尾，因此在建AC自动机的时候，每个结点的val值还要加上其pre结点的val值。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+;

 int n,m,ka;

 char s[N];

 struct AC {

     static const int N=+,M=;

     int go[N][M],pre[N],tot,val[N];

     ll d[][(<<)+][N],ans;

     int idx(char ch) {return ch-'a';}

     void init() {tot=; newnode();}

     int newnode() {

         int u=tot++;

         memset(go[u],,sizeof go[u]);

         val[u]=pre[u]=;

         return u;

     }

     void ins(char* s,int x) {

         int u=,n=strlen(s);

         for(int i=; i<n; u=go[u][idx(s[i])],++i)

             if(!go[u][idx(s[i])])go[u][idx(s[i])]=newnode();

         val[u]|=<<x;

     }

     void build() {

         queue<int> q;

         for(int i=; i<M; ++i)if(go[][i])q.push(go[][i]);

         while(!q.empty()) {

             int u=q.front();

             q.pop();

             val[u]|=val[pre[u]];

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

                 if(go[u][i]) {

                     pre[go[u][i]]=go[pre[u]][i];

                     q.push(go[u][i]);

                 } else go[u][i]=go[pre[u]][i];

             }

         }

     }

     ll dp(int l,int S,int u) {

         if(l==n)return S==(<<m)-?:;

         ll& ret=d[l][S][u];

         if(~ret)return ret;

         ret=;

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

             int v=go[u][i];

             ret+=dp(l+,S|val[v],v);

         }

         return ret;

     }

     void dfs(int l,int S,int u) {

         if(l==n) {

             if(S==(<<m)-)s[l]='\0',puts(s);

             return;

         }

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

             int v=go[u][i];

             if(d[l+][S|val[v]][v])s[l]=i+'a',dfs(l+,S|val[v],v);

         }

     }

     void run() {

         memset(d,-,sizeof d);

         ans=dp(,,);

         printf("%lld suspects\n",ans);

         if(ans<=)dfs(,,);

     }

 } ac;

 int main() {

     while(scanf("%d%d",&n,&m)&&n) {

         printf("Case %d: ",++ka);

         ac.init();

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

             scanf("%s",s);

             ac.ins(s,i);

         }

         ac.build();

         ac.run();

     }

     return ;

 }

巴特西

UVALive - 4126 Password Suspects (AC自动机+状压dp)

最新文章

热门文章