题意

给出n个字符串，求有多少个长度为L的字符串满足每个字符串出现至少一次。字符串仅由小写字母组成。 若方案书<=42的输出方案。 n<=10,L<=25,字符串长度<=10

分析

首先把重复和被包含的字符串去掉，建立AC自动机。 设f[i,j,k]表示在AC自动机上走了i步，走到第j个点，n个字符串的出现情况为k（k为n位二进制）的方案数。直接枚举转移即可。 输出方案数的话，注意到若字符串的某一个位不属于n个字符串中的任何一个，则方案数必然>=52，所以这必然是由n个字符串通过某种排列顺序紧凑排列后得到的。那么我们只要枚举字符串的排列顺序后按照字典序输出即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL; int n,L,ch[105][26],num[105],fail[105],sz,bin[15],bor[15][15],g1,g[15],a1,len[15],rank[50],m; queue<int> que; char str[15][15],a[50][30]; LL f[2][105][1105]; bool vis[15],del[15]; int find(int x,int y) { for (int i=min(len[x],len[y]);i>=0;i--) { int flag=0; for (int j=0;j<i;j++) if (str[x][len[x]-i+j]!=str[y][j]) { flag=1;break; } if (!flag) return i; } } void ins(int x) { int now=0; for (int i=0;i<len[x];i++) if (!ch[now][str[x][i]-'a']) now=ch[now][str[x][i]-'a']=++sz; else now=ch[now][str[x][i]-'a']; num[now]=x; } void get_fail() { for (int i=0;i<26;i++) if (ch[0][i]) que.push(ch[0][i]); while (!que.empty()) { int u=que.front();que.pop(); for (int i=0;i<26;i++) { int v=ch[u][i],k=ch[fail[u]][i]; if (v) fail[v]=k,que.push(v); else ch[u][i]=k; } } } void dfs(int x) { if (x>m) { a1++; int l=0; for (int i=1;i<=g1;i++) for (int j=bor[g[i-1]][g[i]];j<len[g[i]];j++) a[a1][++l]=str[g[i]][j]; if (l!=L) a1--; return; } for (int i=1;i<=n;i++) if (!del[i]&&!vis[i]) vis[i]=1,g[++g1]=i,dfs(x+1),vis[i]=0,g1--; } bool cmp(int x,int y) { for (int i=1;i<=L;i++) if (a[x][i]<a[y][i]) return 1; else if (a[x][i]>a[y][i]) return 0; return 0; } void dp() { bin[0]=1; for (int i=1;i<=n;i++) bin[i]=bin[i-1]*2; f[0][0][0]=1; int now=0; for (int i=0;i<L;i++) { now=1-now; memset(f[now],0,sizeof(f[now])); for (int j=0;j<=sz;j++) for (int k=0;k<bin[n];k++) if (f[now^1][j][k]) for (int l=0;l<26;l++) { int x=ch[j][l],y=k; if (num[x]) y|=bin[num[x]-1]; f[now][x][y]+=f[now^1][j][k]; } } LL ans=0; int s=0; for (int i=1;i<=n;i++) if (!del[i]) s+=bin[i-1]; for (int i=0;i<=sz;i++) ans+=f[now][i][s]; printf("%lld\n",ans); if (ans<=42) { dfs(1); for (int i=1;i<=a1;i++) rank[i]=i; sort(rank+1,rank+a1+1,cmp); for (int i=1;i<=a1;i++) { for (int j=1;j<=L;j++) putchar(a[rank[i]][j]); puts(""); } } } bool check(int x,int y) { for (int i=0;i<=len[y]-len[x];i++) { int j=0; for (j=0;j<len[x];j++) if (str[x][j]!=str[y][i+j]) break; if (j==len[x]) return 1; } return 0; } int main() { scanf("%d%d",&L,&n);m=n; for (int i=1;i<=n;i++) scanf("%s",str[i]),len[i]=strlen(str[i]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { bor[i][j]=find(i,j); if (j>i&&!del[j]&&bor[i][j]==len[i]&&!del[i]) del[i]=1,m--; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (len[j]>len[i]&&!del[j]&&!del[i]&&check(i,j)) del[i]=1,m--; for (int i=1;i<=n;i++) if (!del[i]) ins(i); get_fail(); dp(); return 0; }