Steven_MengのBlog

首先,观察到 $n \le 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();
}

 评论