分析

发现这个是与字串有关系的，就考虑后缀自动机和 自动机。我们发现对于这个问题后缀自动机使用会非常的不自然，因为我们并没有一个原串。我们就考虑如何用 自动机解决。我们可以把所有的目标串插入自动机。因为 所以结尾并没有太多状态，可以考虑状压 。令 为考虑到节点 ，现在状态为 的最小串。那么我们就只需要在 自动机上做转移就可以了，在构建 指针时，因为 指向的是当前串的最大后缀。所以我们有了第一个转移 。那么我们做一次 就可以满足长度最短，从小到大枚举字母就可以满足字典序最小这个条件。那么当我们找到第一个 其中 。那么证明它满足了所以串，这个时候递归输出就好了。每个节点的输出可以考虑数组模拟链表处理，否则空间复杂度可能过不去。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 100,M = 1e7 + 10;
int fail[N],ch[N][26],fa[M],A[M],f[N];
int size,n;
char S[N];
bool vis[N][20005];
#define P pair<int,int>
void insert(char *a,int id) {
    int len = strlen(a);int u = 0;
    for(int i = 0;i < len;i++) {
        int c = a[i] - 'A';
        if(!ch[u][c]) ch[u][c] = ++size;
        // cout <<a[i]<<" now: " << ch[u][c] << endl;
        u = ch[u][c];
    }

    f[u] |= (1<<id-1);
}
void build() {
    queue<int> q;
    for(int i = 0;i < 26;i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = 0;i < 26;i++) {
            int v = ch[u][i];
            if(v) {
                fail[v] = ch[fail[u]][i];
                f[v] |= f[ch[fail[u]][i]];q.push(v);
            }
            else ch[u][i] = ch[fail[u]][i];
        }
    }
    // for(int i = 1;i <= size;i++) cout << fail[i] << " " << f[i] << endl;
}
void print(int x) {
    if(fa[x]) print(fa[x]);
    printf("%c",A[x]+'A');
}
void solve() {
    queue<P> q;int xzc = 0,Id = 0;
    vis[0][0] = 1;q.push(P(0,0));
    while(!q.empty()) {
        P x = q.front();q.pop();
        if(x.second == (1<<n)-1) {
            print(Id);printf("\n");
            return;
        }
        for(int i = 0;i < 26;i++) {
            int v = ch[x.first][i];
            int state = x.second|f[v];
            if(vis[v][state]) continue;
            vis[v][state] = 1;
            fa[++xzc] = Id;A[xzc] = i;
            q.push(P(v,state));
        }
        Id++;
    }
}
int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%s",S);insert(S,i);
    }
    build();
    solve();
    return 0;
}