首先,观察到 n≤12 ,可以想到状压,我们用 f(u,sta) 表示可不可能走到 AC 自动机上节点 i ,并且状态为 sta 的字符串已经是现在串的字串。并且,通过 BFS ,我们可以保证串的长度最短。
关键在于如何找出方案,我们记录 pre(u,sta) 二元组,代表 f(u,sta) 是由哪个状态转移而来的。再记录 child(u,sta) 代表 f(u,sta) 通过字符 child(u,sta) 转移而来。
这样我们的输出方案可以写成递归形式:
1 2 3 4 5
| void Print(pair<int,int>p){ if (!(p.first+p.second)) return ; Print(pre[p.first][p.second]); putchar(child[p.first][p.second]+'A'); }
|
注意代码细节:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #include <bits/stdc++.h> #define MAXN 1005 #define MAXM 37 #define MAXK (1<<14)+5 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+(ch-'0'); ch=getchar(); } return x*f; } char s[MAXN]; int n,tot; namespace AC_Automation{ int trie[MAXN][MAXM],fail[MAXN*MAXM],sta[MAXN*MAXM]; void Insert(char *s,int id){ int len=strlen(s),root=0; for (int i=0;i<len;++i){ int c=s[i]-'A'; if (!trie[root][c]) trie[root][c]=++tot; root=trie[root][c]; } sta[root]|=(1<<id); } void BuildFail(){ queue<int>Q; for (int i=0;i<26;++i){ if (trie[0][i]) Q.push(trie[0][i]),fail[trie[0][i]]=0; } while (Q.size()){ int now=Q.front();Q.pop(); sta[now]|=sta[fail[now]]; for (int i=0;i<26;++i){ int &child=trie[now][i]; if (child){ fail[child]=trie[fail[now]][i]; Q.push(child); } else { child=trie[fail[now]][i]; } } } } bool dp[MAXN][MAXK]; int child[MAXN][MAXK]; pair<int,int> pre[MAXN][MAXK]; void Print(pair<int,int>p){ if (!(p.first+p.second)) return ; Print(pre[p.first][p.second]); putchar(child[p.first][p.second]+'A'); } void BFS(){ queue<pair<int,int> >Q; Q.push(make_pair(0,0)); dp[0][0]=1; while (Q.size()){ int u=Q.front().first,status=Q.front().second; Q.pop(); if (status==((1<<n)-1)){ Print(make_pair(u,status)); puts(""); exit(0); } for (int i=0;i<26;++i){ int v=trie[u][i]; int t=status|sta[v]; if (dp[v][t]==0){ dp[v][t]=1; pre[v][t]=make_pair(u,status); child[v][t]=i; Q.push(make_pair(v,t)); } } } } } using namespace AC_Automation; int main(){ n=read(); for (int i=1;i<=n;++i){ scanf("%s",s); Insert(s,i-1); } BuildFail(); BFS(); }
|