看到题面肯定先搞个AC自动机
考虑一位一位填字符
那么在自动机上就是一位一位匹配
考虑什么时候包含了所有子串
显然是经过了所有的结束标记（当然fail上的也算经过）
最多只有11个单词
考虑状态压缩
经过第 i 个单词结尾就把状态的第 i 位 | 1
然后就可以广搜找了
因为扩展是从 A 到 Z
所以一旦找到了就是字典序最小的答案
但是存答案也有点麻烦，具体还是看代码吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; const int N=1e5+7; const int M=2e6+7; int n; int c[N][27],pd[N],fail[N],cnt; char a[N]; inline void ins(int k) { int u=0,len=strlen(a); for(int i=0;i<len;i++) { int v=a[i]-'A'+1; if(!c[u][v]) c[u][v]=++cnt; u=c[u][v]; } pd[u]|=(1<<k);//注意是 '|=' 可能有重复的单词 } queue <int> qa; void pre() { for(int i=1;i<=26;i++) if(c[0][i]) qa.push(c[0][i]); while(!qa.empty()) { int u=qa.front(); qa.pop(); for(int i=1;i<=26;i++) { int &v=c[u][i]; if(!v) c[u][i]=c[fail[u]][i]; else { fail[v]=c[fail[u]][i]; pd[v]= (pd[v]|pd[fail[v]]);//把fail上的状态也转过来 qa.push(v); } } } } struct node{ int pos,v,id;//pos是AC机上的位置，v是当前状态，id是编号 };//搜索的状态 queue <node> qb; bool f[1007][1<<12];//记忆化数组，是否到过AC机上第i个点时状态为j int from[M],b[M],tot;//存答案，from存编号为i时上一个位置的编号，b存当前编号时的字符 void print(int &x)//递归输出答案 { if(!x) return; print(from[x]); printf("%c",b[x]+'A'-1); } void bfs() { qb.push((node){0,0,0}); while(!qb.empty()) { node x=qb.front(); qb.pop(); if(x.v==((1<<n)-1))//如果找到答案 { print(x.id);//输出 return; } for(int i=1;i<=26;i++) { int &pos=c[x.pos][i],v=x.v|pd[pos]; if(f[pos][v]) continue;//记忆化 f[pos][v]=1; from[++tot]=x.id; b[tot]=i; qb.push((node){pos,v,tot}); } } } int main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%s",a); ins(i-1); } pre(); bfs(); return 0; }