UVALive

给你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值。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=25+5;
 5 int n,m,ka;
 6 char s[N];
 7 
 8 struct AC {
 9     static const int N=100+10,M=26;
10     int go[N][M],pre[N],tot,val[N];
11     ll d[27][(1<<10)+10][N],ans;
12     int idx(char ch) {return ch-'a';}
13     void init() {tot=0; newnode();}
14     int newnode() {
15         int u=tot++;
16         memset(go[u],0,sizeof go[u]);
17         val[u]=pre[u]=0;
18         return u;
19     }
20     void ins(char* s,int x) {
21         int u=0,n=strlen(s);
22         for(int i=0; i<n; u=go[u][idx(s[i])],++i)
23             if(!go[u][idx(s[i])])go[u][idx(s[i])]=newnode();
24         val[u]|=1<<x;
25     }
26     void build() {
27         queue<int> q;
28         for(int i=0; i<M; ++i)if(go[0][i])q.push(go[0][i]);
29         while(!q.empty()) {
30             int u=q.front();
31             q.pop();
32             val[u]|=val[pre[u]];
33             for(int i=0; i<M; ++i) {
34                 if(go[u][i]) {
35                     pre[go[u][i]]=go[pre[u]][i];
36                     q.push(go[u][i]);
37                 } else go[u][i]=go[pre[u]][i];
38             }
39         }
40     }
41     ll dp(int l,int S,int u) {
42         if(l==n)return S==(1<<m)-1?1:0;
43         ll& ret=d[l][S][u];
44         if(~ret)return ret;
45         ret=0;
46         for(int i=0; i<M; ++i) {
47             int v=go[u][i];
48             ret+=dp(l+1,S|val[v],v);
49         }
50         return ret;
51     }
52     void dfs(int l,int S,int u) {
53         if(l==n) {
54             if(S==(1<<m)-1)s[l]='',puts(s);
55             return;
56         }
57         for(int i=0; i<M; ++i) {
58             int v=go[u][i];
59             if(d[l+1][S|val[v]][v])s[l]=i+'a',dfs(l+1,S|val[v],v);
60         }
61     }
62     void run() {
63         memset(d,-1,sizeof d);
64         ans=dp(0,0,0);
65         printf("%lld suspects
",ans);
66         if(ans<=42)dfs(0,0,0);
67     }
68 } ac;
69 
70 int main() {
71     while(scanf("%d%d",&n,&m)&&n) {
72         printf("Case %d: ",++ka);
73         ac.init();
74         for(int i=0; i<m; ++i) {
75             scanf("%s",s);
76             ac.ins(s,i);
77         }
78         ac.build();
79         ac.run();
80     }
81     return 0;
82 }