Description
Input
Output
Sample Input
10 2
hello
world
Sample Output
2
helloworld
worldhello
HINT
一看(n)这么小就要状压……我们设(f[i][j][s])表示长度为(i)，AC自动机上节点为(j)，出现的字符串的状态为(s)的方案数，然后直接枚举转移即可
然后难点就在于如何输出方案
首先42这数字非常妙(生命、宇宙以及任何事情的终极答案)
如果存在一个字符可以任意选的情况，那么答案至少也要为2*26=52，所以这种情况是不存在的
所以就直接爆搜，(O(n!))搜索，然后中间疯狂剪枝就好
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1;char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1e2;
struct S1{
int trie[N+10][26],fail[N+10],End[N+10];
int root,tot;
void insert(char *s,int ID){
int len=strlen(s),p=root;
for (int i=0;i<len;i++){
if (!trie[p][s[i]-'a']) trie[p][s[i]-'a']=++tot;
p=trie[p][s[i]-'a'];
}
End[p]=1<<ID;
}
void make_fail(){
static int h[N+10];
int head=1,tail=0;
for (int i=0;i<26;i++) if (trie[root][i]) h[++tail]=trie[root][i];
for (;head<=tail;head++){
int Now=h[head];
End[Now]|=End[fail[Now]];
for (int i=0;i<26;i++){
if (trie[Now][i]){
int son=trie[Now][i];
fail[son]=trie[fail[Now]][i];
h[++tail]=son;
}else trie[Now][i]=trie[fail[Now]][i];
}
}
}
}AC;//Aho-Corasick automaton
int work(char *s,char *t){
int lens=strlen(s),lent=strlen(t),Ans=0;
for (int i=0;i<lens;i++){
int res=0,x=i,y=0;
while (x<lens&&y<lent){
if (s[x]!=t[y]) break;
res++,x++,y++;
}
if (x!=lens) continue;
Ans=max(Ans,res);
}
return Ans;
}
ll f[30][N+10][(1<<10)+10];
int pos[15],Len[15],g[15][15],L,n,cnt;
bool vis[15];
char s[15][15];
struct S2{char s[N+10];}A[50];
bool operator <(const S2 &x,const S2 &y){
int lenx=strlen(x.s),leny=strlen(y.s);
if (lenx!=leny) return lenx<leny;
for (int i=0;i<lenx;i++) if (x.s[i]!=y.s[i]) return x.s[i]<y.s[i];
return 0;
}
void dfs(int x,int len){
if (len>L) return;
if (x==n){
static char T[N+10];
for (int i=0;i<Len[pos[0]];i++) T[i]=s[pos[0]][i];
int L=Len[pos[0]];
for (int i=1;i<n;i++){
for (int j=0;j<Len[pos[i]];j++)
T[j+L-g[pos[i-1]][pos[i]]]=s[pos[i]][j];
L+=Len[pos[i]]-g[pos[i-1]][pos[i]];
}
memcpy(A[cnt++].s,T,sizeof(T));
return;
}
for (int i=0,tmp;i<n;i++){
if (!vis[i]){
pos[x]=i,vis[i]=1;
tmp=len+Len[i]-(x?g[pos[x-1]][i]:0);
dfs(x+1,tmp);
pos[x]=0,vis[i]=0;
}
}
}
int main(){
L=read(),n=read();
for (int i=0;i<n;i++){
scanf("%s",s[i]);
Len[i]=strlen(s[i]);
AC.insert(s[i],i);
}
AC.make_fail();
f[0][0][0]=1;
for (int i=0;i<L;i++){
for (int j=0;j<=AC.tot;j++){
for (int s=0;s<1<<n;s++){
if (!f[i][j][s]) continue;
for (int k=0;k<26;k++){
int son=AC.trie[j][k];
f[i+1][son][s|AC.End[son]]+=f[i][j][s];
}
}
}
}
ll Ans=0;
for (int i=0;i<=AC.tot;i++) Ans+=f[L][i][(1<<n)-1];
printf("%lld
",Ans);
if (Ans>42) return 0;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
g[i][j]=work(s[i],s[j]);
dfs(0,0);
sort(A,A+cnt);
for (int i=0;i<cnt;i++) printf("%s
",A[i].s);
return 0;
}