题目
题目描述
众所周知，密码在信息领域起到了不可估量的作用。对于普通的登陆口令以，唯一的破解方法就是暴力破解——逐个尝试所有可能的字母组合，但这是一项很耗时又容易被发现的工作。所以，为了获取对方的登陆口令，在暴力破解密码之前，必须先做大量的准备工作。经过情报的搜集，现在得到了若干有用信息，形如：
“我观察到，密码中含有字符串*。”
例如，对于一个10位的密码以及观察到的字符串hello与world,可能的密码组合为helloworld与worldhello;而对于6位的密码以及到的字符串good与day,可能的密码组合为gooday。
有了这些信息，就能够大大地减少尝试的次数了。请编一个程序，计算所有密码组合的可能。密码中仅可能包含a-z之间的小写字母。
输入输出格式
输入格式：
输入数据首先输入两个整数L,N，分别表示密码的长度与观察到子串的个数。
接下来N行，每行若干个字符，描述了每个观察到的字符串。
输出格式：
输出数据第一行为一个整数，代表了满足所有观察条件字符串的总数。
若这个数字小于等于42，则按字典顺序输出所有密码的可能情况，每行一个，否则，只输出满足所有观察条件字符串的总数即可。
输入输出样例
输入样例#1：
10 2
hello
world
输出样例#1：
2
helloworld
worldhello
说明
对于100%的数据，1<=L<=25,1<=N<=10,每个观察到的字符串长不超过10，并且保证输出结果小于2^63。
题解
首先先不管输出每种情况，建出$AC$自动机后，$f_{i,j,k}$表示前$i$位时状态为$j$已经出现过状态$k$（状态压缩）的给定字符串的方案数
最终的答案就是$\sum_{i=0}^{N}f_{L,i,(1«n)-1}$，$N$是$AC$自动机节点数
现在看不大于$42$的答案怎么输出
因为如果一个位置是不确定的，最少能产生$52$种答案
所以答案就是$n$个字符串的排列再处理重叠的部分
爆搜套爆搜加一点剪枝就行了（并不）
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int N=105,M=(1<<10)+1;
struct p{
char a[31];
}Ans[N];
int L,n,tot,_N,cnt;
int qu[N],A[N],D[N],Len[N],tax[N],Id[N];
int _D[N][N];
LL f[31][N][M];
char a[11][11];
bool use[N];
bool cmp(p a,p b)
{
for(int i=1;i<=L;++i)
if(a.a[i]<b.a[i]) return 1;
else if(a.a[i]>b.a[i]) return 0;
return 1;
}
bool look(int id,int x,int y)
{
for(int i=id,j=1;i<=Len[x];++i,++j)
if(a[x][i]!=a[y][j]) return 0;
return 1;
}
int look(int x,int y)
{
if(_D[x][y]!=-1) return _D[x][y];
for(int i=1;i<=Len[x];++i)
if(look(i,x,y)) return _D[x][y]=Len[x]-i+1;
return 0;
}
void Dfs(int ans,int x=1,int d=_N-L)
{
if(x==n)
{
if(d) return;
++cnt;
for(int i=1;i<=Len[A[1]];++i)
Ans[cnt].a[i]=a[A[1]][i];
int _cnt=Len[A[1]];
for(int i=2;i<=n;++i)
for(int j=D[i]+1;j<=Len[A[i]];++j)
Ans[cnt].a[++_cnt]=a[A[i]][j];
return;
}
if(cnt==ans) return;
for(int i=min(d,look(A[x],A[x+1]));i>=0;--i)
D[x+1]=i,Dfs(ans,x+1,d-i);
}
void dfs(int ans,int x=0)
{
if(x==n) return void(Dfs(ans));
if(cnt==ans) return;
for(int i=0;i<n;++i)
if(!use[i]) use[i]=1,A[x+1]=i,dfs(ans,x+1),use[i]=0;
}
struct AC{
int fail[N],val[N];
int son[N][26];
void ins(int _L,int id)
{
int x=0;
for(int i=1;i<=_L;++i)
if(son[x][a[id][i]-'a']) x=son[x][a[id][i]-'a'];
else son[x][a[id][i]-'a']=++tot,x=tot;
val[x]=1<<id,_N+=_L,Len[id]=_L;
}
void GET_FAIL()
{
int hl=1,tl=0;
for(int i=0;i<26;++i)
if(son[0][i]) qu[++tl]=son[0][i];
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=0;i<26;++i)
if(son[tt][i]) fail[son[tt][i]]=son[fail[tt]][i],qu[++tl]=son[tt][i];
else son[tt][i]=son[fail[tt]][i];
val[tt]|=val[fail[tt]];
}
}
void Solve()
{
GET_FAIL(),f[0][0][0]=1;
for(int k=1;k<=L;++k)
for(int i=0;i<=tot;++i)
for(int j=0;j<26;++j)
for(int h=0;h<(1<<n);++h)
f[k][son[i][j]][h|val[son[i][j]]]+=f[k-1][i][h];
LL ans=0;
for(int i=0;i<=tot;++i)
ans+=f[L][i][(1<<n)-1];
printf("%lld\n",ans);
if(ans<=42)
{
memset(_D,-1,sizeof(_D));
dfs(ans),sort(Ans+1,Ans+1+cnt,cmp);
for(int i=1;i<=cnt;++i,printf("\n"))
for(int j=1;j<=L;++j)
printf("%c",Ans[i].a[j]);
}
}
}_A;
int main()
{
scanf("%d%d",&L,&n);
for(int i=0,_n;i<n;++i)
scanf("%s",a[i]+1),_A.ins(strlen(a[i]+1),i);
return _A.Solve(),0;
}
