AC自动机+bfs
题目要求：在AC自动机建的Trie图上找到一条最短链，包含所有带结尾标记的点
因为n<12，所以我们可以用二进制保存状态：某个带结尾标记的点是否被处理到。
把编号为 i 的结尾标记设为2^(i-1)
然后跑一遍bfs，如果跑到某个点结尾标记之和=2^n-1，那么就说明答案找到了
开2个数组保存每个bfs状态的对应的上一个编号和对应字母
输出的时候递归即可
attention：保存bfs状态的数组一定要开的很大（2e5/1e6/2e6 70pts/90pts/AC）
对于字典序问题：查找顺序都是'A'->‘Z’，不用担心（我还瞎操心个啥qaq）
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct data{ int nxt[26],fail,last,end; }a[602]; struct node{int id,t,state;}; char q[55]; int n,cnt1,cnt2,pre1[2000001],pre2[2000001]; bool vis[4097][602]; inline void Trie_build(int id){ scanf("%s",q); int u=0,len=strlen(q); for(int i=0;i<len;++i){ int p=q[i]-'A'; if(!a[u].nxt[p]) a[u].nxt[p]=++cnt1; u=a[u].nxt[p]; }a[u].end|=1<<(id-1); //标记值=2^(i-1) } void AC_build(){ queue <int> h; for(int i=0;i<26;++i) if(a[0].nxt[i]) h.push(a[0].nxt[i]); while(!h.empty()){ int x=h.front(); h.pop(); for(int i=0;i<26;++i){ int &to=a[x].nxt[i]; if(to){ a[to].fail=a[a[x].fail].nxt[i]; a[to].last= a[a[to].fail].end ? a[to].fail:a[a[to].fail].last; a[to].end|=a[a[to].last].end; //累加上所有后缀的状态 h.push(to); }else to=a[a[x].fail].nxt[i]; } } } inline void print(int x){ //递归输出 if(!x) return; print(pre1[x]); putchar(pre2[x]+'A'); } void bfs(){ queue <node> h; h.push((node){0,0,a[0].end}); while(!h.empty()){ node x=h.front(); h.pop(); if(x.state==(1<<n)-1) {print(x.t); return ;} for(int i=0;i<26;++i){ //字典序从小到大 node to=(node){a[x.id].nxt[i],233,x.state|a[a[x.id].nxt[i]].end}; //状态更新 if(vis[to.state][to.id]) continue; //去重 vis[to.state][to.id]=1; to.t=++cnt2; //给一个新编号 pre1[cnt2]=x.t; pre2[cnt2]=i; //用两个数组存该编号对应的字母和上级的编号 h.push(to); } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) Trie_build(i); AC_build(); bfs(); return 0; }