BZOJ1195 LOJ10061
题目大意：给你$n$个模式串，求一个最短且字典序最小的文本串并输出这个串，$n<=12,len<=50$
首先对所有模式串构造$Trie$图，$Trie$图的性质和$DP$的性质简直是完美契合..
模式串数量很少，考虑状压
定义$f[x][s]$表示现在所在$Trie$图内的位置为$x$，已经匹配到的串的状态为$s$，此时需要文本串的最短长度
转移十分显然，$f[fail_{x}][s|ed[fail_{x}])]=min(f[x][s])+1$
最后找出最小的$f[x][(1<
然而...直接这样转移我们没办法统计答案啊
考虑把问题放到图上，利用$bfs$队列先进先出的性质，如果我们优先把字典序小的状态推进队列，再通过记录当前状态第一次被更新时的上一层状态$fa[..]$的方式记录路径，跑$bfs$最短路，当队列中出现$s==(1<
注意可能有相同的串
注意不要忘了建$fail$树，如果某个节点是某个串的结尾，也要把它是这个串的结尾的信息传递到它在$fail$树中的子树中去！我没传竟然还有70分
1 #include
2 #include
3 #include
4 #include
5 #define NN 610
6 #define MM 4100
7 #define ll long long
8 #define uint unsigned int
9 #define ull unsigned long long
10 #define inf 0x3f3f3f3f
11 #define idx(x) (x-'A')
12 using namespace std;
13
14 int n,cte;
15 int head[NN];
16 char str[NN];
17 struct Edge{int to,nxt;}edge[NN*2];
18 void ae(int u,int v){
19 cte++;edge[cte].nxt=head[u];
20 edge[cte].to=v,head[u]=cte;
21 }
22 struct node{
23 int x,s;
24 node(int x,int s):x(x),s(s){}
25 node(){}
26 }fa[NN][MM];
27 int dis[NN][MM];
28 namespace AC{
29 int ch[NN][26],fail[NN],ed[NN],val[NN],tot;
30 void Build_Trie(char *str,int len,int id)
31 {
32 int x=0;
33 for(int i=1;i<=len;i++){
34 if(!ch[x][idx(str[i])])
35 ch[x][idx(str[i])]=++tot,val[tot]=idx(str[i]);
36 x=ch[x][idx(str[i])];
37 }ed[x]|=(1<<(id-1));
38 }
39 void Build_Fail()
40 {
41 queue<int>q;
42 for(int i=0;i<26;i++)
43 if(ch[0][i]) q.push(ch[0][i]);
44 while(!q.empty())
45 {
46 int x=q.front();q.pop();
47 ae(fail[x],x);
48 for(int i=0;i<26;i++)
49 {
50 if(ch[x][i]){
51 fail[ch[x][i]]=ch[fail[x]][i];
52 q.push(ch[x][i]);
53 }else{
54 ch[x][i]=ch[fail[x]][i];
55 }
56 }
57 }
58 q.push(0);
59 while(!q.empty())
60 {
61 int x=q.front();q.pop();
62 for(int j=head[x];j;j=edge[j].nxt){
63 int v=edge[j].to;
64 ed[v]|=ed[x];
65 q.push(v);
66 }
67 }
68 }
69 node Bfs()
70 {
71 queueq;
72 memset(dis,0x3f,sizeof(dis));
73 q.push(node(0,0));
74 dis[0][0]=0;
75 node k1,k2;
76 int x,v,s,t;
77 while(!q.empty())
78 {
79 k1=q.front();q.pop();
80 x=k1.x,s=k1.s;
81 if(s==(1<1) return k1;
82 for(int i=0;i<26;i++)
83 {
84 v=ch[x][i],t=s|ed[v];
85 if(dis[v][t]>dis[x][s]+1){
86 dis[v][t]=dis[x][s]+1;
87 fa[v][t]=k1;
88 q.push(node(v,t));
89 }
90 }
91 }
92 /*for(int i=1;i<=tot;i++)
93 printf("%d:%d\n",i,dis[i][(1<*/
94 }
95 char Ans[NN];
96 void solve()
97 {
98 for(int i=1;i<=n;i++){
99 scanf("%s",str+1);
100 int len=strlen(str+1);
101 Build_Trie(str,len,i);}
102 Build_Fail();
103 node ans=Bfs();
104 node a=ans;
105 int num=0;
106 while(a.x||a.s){
107 Ans[++num]=val[a.x]+'A';
108 a=fa[a.x][a.s];}
109 for(int i=num;i>0;i--)
110 printf("%c",Ans[i]);
111 puts("");
112 }
113 };
114
115 int main()
116 {
117 //freopen("t2.in","r",stdin);
118 scanf("%d",&n);
119 AC::solve();
120 return 0;
121 }