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 0x7f7f7f7fusing 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 automatonint 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\n",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\n",A[i].s); ???return 0;}[JSOI2009]密码
原文地址：https://www.cnblogs.com/Wolfycz/p/10486372.html