题意：训练指南P250
分析：DFS记忆化搜索，范围或者说是图是已知的字串构成的自动机图，那么用 | (1 << i)表示包含第i个字串，如果长度为len，且st == (1 << m) - 1则是可能的。打印与之前相似。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 25 + 5;
const int NODE = 10 * 10 + 5;
const int M = (1 << 10) + 5;
const int SIZE = 26; int n, m;
char str[12];
struct AC {
int ch[NODE][SIZE], val[NODE], fail[NODE], last[NODE], sz;
ll dp[NODE][N][M]; int out[N];
void clear(void) {
memset (ch[0], 0, sizeof (ch[0]));
sz = 1;
}
int idx(char c) {
return c - 'a';
}
void insert(char *s, int v) {
int u = 0;
for (int c, i=0; s[i]; ++i) {
c = idx (s[i]);
if (!ch[u][c]) {
memset (ch[sz], 0, sizeof (ch[sz]));
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] |= (1 << v);
}
void build(void) {
queue<int> que; fail[0] = 0;
for (int c=0; c<SIZE; ++c) {
int u = ch[0][c];
if (u) {
fail[u] = 0; last[u] = 0;
que.push (u);
}
}
while (!que.empty ()) {
int r = que.front (); que.pop ();
for (int c=0; c<SIZE; ++c) {
int &u = ch[r][c];
if (!u) {
u = ch[fail[r]][c]; continue;
}
que.push (u);
int v = fail[r];
while (v && !ch[v][c]) v = fail[v];
fail[u] = ch[v][c];
val[u] |= val[fail[u]];
//last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void print(int now, int len, int st) {
if (len == n) {
for (int i=0; i<len; ++i) {
printf ("%c", out[i] + 'a');
}
puts (""); return ;
}
for (int c=0; c<SIZE; ++c) {
if (dp[ch[now][c]][len+1][st|val[ch[now][c]]] > 0) {
out[len] = c;
print (ch[now][c], len + 1, st | val[ch[now][c]]);
}
}
}
ll DP(int now, int len, int st) {
ll &ans = dp[now][len][st];
if (ans != -1) return ans;
if (len == n) {
if (st == (1 << m) - 1) return ans = 1;
else return ans = 0;
}
ans = 0;
for (int c=0; c<SIZE; ++c) {
ans += DP (ch[now][c], len + 1, st | val[ch[now][c]]);
}
return ans;
}
void run(void) {
memset (dp, -1, sizeof (dp));
ll ans = DP (0, 0, 0);
printf ("%lld suspects\n", ans);
if (ans <= 42) {
print (0, 0, 0);
}
}
}ac; int main(void) {
int cas = 0;
while (scanf ("%d%d", &n, &m) == 2) {
if (!n && !m) break;
ac.clear ();
for (int i=0; i<m; ++i) {
scanf ("%s", &str);
ac.insert (str, i);
}
ac.build ();
printf ("Case %d: ", ++cas);
ac.run ();
} return 0;
}