给你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 ;
}