图片加载可能有点慢,请跳过题面先看题解,谢谢
一看到这么多模式串就非常兴奋,又是\(AC\)自动机
题目就是要求:经过 \(n\) 个节点,把所有单词都遍历一遍的方案数,和那道题差不多嘛
所以这样设:\(f[i][j][k]\) 为,走了 \(i\) 个节点,当前点在 \(j\),单词的经过情况为 \(k\)(一个二进制数)时的方案数
答案很显然是:\(\sum_{i=1}^{size}f[n][i][(1<<m)-1]\)
转移也很显然:\(f[i+1][Son][s|val[Son]]+=f[i][j][s]\)
$
$
但是这道题有点麻烦的就是,它需要输出方案,上面那样子做不太好记录路径
这里考虑反过来搞,这样转移:\(f[i][j][s]+=f[i+1][Son][s|val[Son]]\),答案就变成了\(f[0][0][0]\)
这样做的话,就可以保证只有在有效路径上,\(f\) 值才不为\(0\),那么方案就很好办了
$
$
//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#define ll long long
using namespace std;
int t,n,m;
struct Trie{
char o[26];
int root,size;
ll f[26][110][1<<10];
int son[110][30],fail[110],val[110];
void init(){
size=1; root=0;
memset(son,0,sizeof(son));
memset(val,0,sizeof(val));
memset(fail,0,sizeof(fail));
memset(f[n],0,sizeof(f[n]));
}
int idx(char c){ return c-'a'; }
void insert(char* s,int v){
int cur=root;
for(int i=0;s[i];i++){
int id=idx(s[i]);
if(!son[cur][id]) son[cur][id]=size++;
cur=son[cur][id];
}
val[cur]|=1<<v; return ;
}
void build(){
int que[110];
int hd=0,tl=0;
for(int i=0;i<26;i++)
if(son[root][i]){
fail[son[root][i]]=root;
que[tl++]=son[root][i];
}
else son[root][i]=root;
while(hd<tl){
int cur=que[hd++];
for(int i=0;i<26;i++){
int Son=son[cur][i];
if(Son){
int f=fail[cur];
while(f && !son[f][i]) f=fail[f];
fail[Son]=son[f][i];
val[Son]|=val[fail[Son]];
que[tl++]=Son;
}
else son[cur][i]=son[fail[cur]][i];
}
}
}
ll dp(){
for(int i=0;i<size;i++) f[n][i][(1<<m)-1]=1;
for(int i=n-1;i>=0;i--)
for(int j=0;j<size;j++)
for(int s=0;s<(1<<m);s++){
f[i][j][s]=0;
for(int k=0;k<26;k++){
int Son=son[j][k];
int ss=s|val[Son];
f[i][j][s]+=f[i+1][Son][ss];
}
}
return f[0][0][0];
}
void print(int i,int j,int s){
if(i==n){
for(int k=0;k<n;k++) printf("%c",o[k]);
puts("");
return ;
}
for(int k=0;k<26;k++){
int Son=son[j][k];
int ss=s|val[Son];
if(f[i+1][Son][ss]){
o[i]=k+'a';
print(i+1,Son,ss);
}
}
}
}AC;
set<string>map;
void init(){
AC.init(),map.clear();
int cnt=0;
for(int i=0;i<m;i++){
char s[15];
scanf("%s",s);
string S=s;
if(!map.count(S)){
AC.insert(s,cnt++);
map.insert(S);
}
}
m=cnt;
}
void work(){
AC.build();
ll ans=AC.dp();
printf("Case %d: %lld suspects\n",++t,ans);
if(ans<=42) AC.print(0,0,0);
}
int main(){ while(scanf("%d%d",&n,&m)&&n){ init(); work(); } return 0; }