自动搬运

查看原文

来自洛谷，原作者为

	skydogli 一个人的命运啊，当然要靠自我奋斗，但也要考虑历史的进程

搬运于2025-08-24 21:36:21，当前版本为作者最后更新于2019-05-14 20:49:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢

主要思路:首先按照平常$AC$自动机的步骤,建出$Trie$图,和各个点的$Fail$指针,这样我们就能通过bfs搜索出所有合法的方案.在建$Trie$图的同时,我们把单词$i$的末节点值$state$为$(1<<i)$,$Bfs$时用当前状态$\color{red} or$遍历到节点的$state$值,当$Bfs$到某个状态等于$(1<<(n)-1)$时,就证明所有的单词的末端点都遍历了一次,那这个搜索到的字符串就是我们想要的答案了.时间复杂度和空间复杂度都是$O(cnt*2^n)$,$cnt$为$Trie$树的节点数,还带$26$的常数

当然,我们把当前搜索到的字符串都存下来是相当消耗空间的,所以我们可以想出$1$个优化:因为所有$Bfs$出的状态都是由前面的状态推导出的,所以我们可以每次搜索时只记录这次搜索的字符和它是由哪个状态推导出的,输出时倒回去统计就行了.

看不懂也没关系我的表达能力我心里有点$*$数, 程序的注释还是比较多的

另外,$90$分的注意了,可能有相同的字符串,所以设state的初值时也要$or(1<<i)$而不是直接赋值

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define MN 605
int add[MN][26],fail[MN],state[MN],nod,ans[MN*(1<<12|1)],fa[MN*(1<<12|1)],n,cnt,tot;
//add:Trie树中的地址(address)
bool vis[MN][1<<12|1];
char C[MN],ch[51];
queue<int>Q,Q1,Q2;
void getfail(){
    for(int i=0;i<26;++i)
        if(add[0][i])Q.push(add[0][i]);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=0;i<26;++i)
            if(add[x][i]){
                fail[add[x][i]]=add[fail[x]][i];
                state[add[x][i]]|=state[add[fail[x]][i]];//它的fail指针包含的字符串它也包含
                Q.push(add[x][i]);
            }
            else add[x][i]=add[fail[x]][i];
    }
}//AC自动机建fail树
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",ch);
        int now=0,ln=strlen(ch);
        for(int j=0;j<ln;++j){
            if(!add[now][ch[j]-'A'])add[now][ch[j]-'A']=++cnt;
            now=add[now][ch[j]-'A'];
        }
        state[now]|=1<<(i-1);//i-1也不会冲突,省一点空间
        //有重复的,要用|
    }//建trie树
    getfail();
    Q1.push(0);
    Q2.push(0);
    //Q1:在Trie中的位置
    //Q2:状态压缩,表示当前包含了哪些要求的字符串
    vis[0][0]=1;
    int Ti=0;
    while(!Q1.empty()){
        int now=Q1.front(),St=Q2.front();
        Q1.pop();Q2.pop();
        if(St==((1<<n)-1)){
            while(Ti){
                C[++nod]=ans[Ti];
                Ti=fa[Ti];
            }//递归回去求答案
            for(int i=nod;i>0;--i)putchar(C[i]+'A');
            return 0;
        }
        for(int i=0;i<26;++i){
            if(!vis[add[now][i]][St|state[add[now][i]]]){
                vis[add[now][i]][St|state[add[now][i]]]=1;
                Q1.push(add[now][i]);
                Q2.push(St|state[add[now][i]]);
                //找出现新的状态
                fa[++tot]=Ti;
                ans[tot]=i;
                //记录当前搜到的字符,同时建1棵关于答案的树,便于最后查询
            }
        }
        ++Ti;//Ti表示当前的搜索到的编号
    }
    return 0;
}