http://www.lydsy.com/JudgeOnline/problem.php?id=1559
2009年的省选题虽然比起现在简单了不少，但对我来说还是很有挑战性的。
首先对于这种多串匹配问题，第一个想到的就应该是AC自动机。
还是老套路，f[i][j]表示走到字符串的第i位，现在在自动机上的第j位时的信息。增加一维n位的压位表示各个串是否都被匹配到了。
但是这里有个问题，如果S1包含了S2，那么我们只需要S1被匹配就能保证S2也被匹配，而不需要在自动机上走到S2的位置。
这样我们预处理的时候先删掉所有被包含的字符串（反正L<=25,N<=10怎样都不会T），然后直接在自动机上跑DP即可。
现在考虑ans<=42的情况，可以发现，这种情况下原串不可能有任何一个自由字母。因为只要存在一个自由字母和一个模式串，则至少存在2*26=52>42种方案。所以对于这种情况我们只需用最暴力的方法DFS穷举所有长度为L且恰好包含了每个模式串的方案并按字典序排序。
这里有一个技巧，border[i][j]表示第i个串后缀和第j个串的前缀中完全匹配的最长的串的长度（也就是KMP中的nxt[]），方便穷举。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define rep(i,l,r) for (int i=l; i<=r; i++) 6 typedef long long ll; 7 using namespace std; 8 ?9 int n,m,L,ch[105][26],q[105],num[105],fail[105],sz,bor[15][15],g1,g[15],a1,len[15],rk[50],vis[15],del[15];10 char str[15][15],a[50][30];11 ll f[2][105][1100];12 13 int border(int x,int y){14 ????for (int i=min(len[x],len[y]); i>=0; i--){15 ????????int flag=0;16 ????????rep(j,0,i-1) if (str[x][len[x]-i+j]!=str[y][j]){ flag=1; break; }17 ????????if (!flag) return i;18 ????}19 ????return 0;20 }21 22 void ins(int x){23 ????int now=0;24 ????rep(i,0,len[x]-1){25 ????????int s=str[x][i]-‘a‘;26 ????????if (!ch[now][s]) ch[now][s]=++sz;27 ????????now=ch[now][s];28 ????}29 ????num[now]=1<<(x-1);30 }31 32 void getfail(){33 ????int st=0,ed=0;34 ????rep(i,0,25) if (ch[0][i]) q[++ed]=ch[0][i];35 ????while (st<ed){36 ????????int x=q[++st];37 ????????rep(i,0,25)38 ????????????if (ch[x][i]) q[++ed]=ch[x][i],fail[ch[x][i]]=ch[fail[x]][i];39 ????????????????else ch[x][i]=ch[fail[x]][i];40 ????}41 }42 43 void dfs(int x){44 ????if (x>m){45 ????????a1++; int l=0;46 ????????rep(i,1,g1) rep(j,bor[g[i-1]][g[i]],len[g[i]]-1) a[a1][++l]=str[g[i]][j];47 ????????if (l!=L) a1--; return;48 ????}49 ????rep(i,1,n) if (!del[i] && !vis[i]) vis[i]=1,g[++g1]=i,dfs(x+1),vis[i]=0,g1--;50 }51 52 bool cmp(int x,int y){53 ????rep(i,1,L) if (a[x][i]!=a[y][i]) return a[x][i]<a[y][i];54 ????return 0;55 }56 57 bool chk(int x,int y){58 ????rep(i,0,len[y]-len[x]){59 ????????int j=0;60 ????????for (; j<len[x]; j++) if ((str[x][j])!=str[y][i+j]) break;61 ????????if (j==len[x]) return 1;62 ????}63 ????return 0;64 }65 66 void dp(){67 ????int now=0; f[0][0][0]=1;68 ????rep(i,0,L-1){69 ????????now=now^1; mem(f[now]);70 ????????rep(j,0,sz) rep(k,0,(1<<n)-1)71 ????????????if (f[now^1][j][k])72 ????????????????rep(l,0,25){73 ????????????????????int x=ch[j][l],y=k;74 ????????????????????if (num[x]) y|=num[x];75 ????????????????????f[now][x][y]+=f[now^1][j][k];76 ????????????????}77 ????}78 ????ll ans=0; int s=0;79 ????rep(i,1,n) if (!del[i]) s+=1<<(i-1);80 ????rep(i,0,sz) ans+=f[now][i][s];81 ????printf("%lld\n",ans);82 ????if (ans<=42){83 ????????dfs(1); rep(i,1,a1) rk[i]=i;84 ????????sort(rk+1,rk+a1+1,cmp);85 ????????rep(i,1,a1){ rep(j,1,L) putchar(a[rk[i]][j]); puts(""); }86 ????}87 }88 89 int main(){90 ????freopen("bzoj1559.in","r",stdin);91 ????freopen("bzoj1559.out","w",stdout);92 ????scanf("%d%d",&L,&n); m=n;93 ????rep(i,1,n) scanf("%s",str[i]),len[i]=strlen(str[i]);94 ????rep(i,1,n) rep(j,1,n) bor[i][j]=border(i,j);95 ????rep(i,1,n) rep(j,1,n) if (len[j]>len[i] && !del[j] && !del[i] && chk(i,j)) del[i]=1,m--;96 ????rep(i,1,n) if (!del[i]) ins(i);97 ????getfail(); dp();98 ????return 0;99 }[BZOJ1559][JSOI2009]密码(AC自动机)
原文地址：https://www.cnblogs.com/HocRiser/p/8591639.html