最短母串问题

题意：给定 n n n个子串，求最短且字典序最小的母串（母串性质：这 n n n个子串都包含在母串里）

思路：

  1. 考虑把子串去重（不去重能不能A我不知道，但去重肯定没问题）
  2. 建好AC自动机
  3. 从 0 0 0节点开始用 b f s bfs bfs遍历自动机，并且总是从’A’遍历到’Z’以保证答案的字典序最下
  4. 每次取出头结点时检查其状态是否包含了所有的子串，状态检查： n o w . s t a t e = = ( 1 &lt; &lt; ( n + 1 ) ) − 2 now.state==(1&lt;&lt;(n+1))-2 now.state==(1<<(n+1))−2
  5. 但仅仅这样的话不是爆内存就是T，毕竟会有很多没必要的搜索。比如某两个字符串，长度不一样，但其 拥有子串的状态 以及 最后一个字符在AC自动机上的位置 却一样，对于这样的两个字符串显然保留较短的字符串，故在考虑将某个字符串加入队列前先检查是否有更优的字符串，若没有，才加入 
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define rt 1,N,1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline ll read() {ll x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e4+10;
const int mod = 1e9+7;
const double eps = 1e-9;

struct P{
    int pos, state;
    string l;
    P() {}
    P(int pos, int state, string l): pos(pos), state(state), l(l) {}
};

int trie[600][26], fail[600], tot, ed[600];
bool vis[600][maxn]; //用vis数组存储AC自动机上每个节点的每个状态是否已经达到
string l[20];

void insert(string l, int id) {
    int len=l.size(), p=0;
    for(int i=0; i<len; ++i) {
        int k=l[i]-'A';
        if(!trie[p][k]) trie[p][k]=++tot;
        p=trie[p][k];
    }
    ed[p]=id;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int n=read();
    for(int i=1; i<=n; ++i) cin>>l[i];
    sort(l+1,l+1+n);
    n=unique(l+1,l+1+n)-l-1;
    for(int i=1; i<=n; ++i) insert(l[i],i);
    build();
    queue<P> q; q.push(P(0,0,"")), vis[0][0]=1;
    while(q.size()) {
        P now=q.front(); q.pop();
        if(now.state==(1<<(n+1))-2) { cout<<now.l<<endl; break; }
        for(int i=0; i<26; ++i) {
            if(!trie[now.pos][i]) continue;
            int s=now.state;
            for(int j=trie[now.pos][i]; j; j=fail[j]) if(ed[j]) s|=1<<ed[j];
            if(!vis[trie[now.pos][i]][s]) q.push(P(trie[now.pos][i],s,now.l+char('A'+i))), vis[trie[now.pos][i]][s]=1; //若遍历过的字符串中没有更优的才加入到队列中
        }
    }
}