题解 P2322 【[HNOI2006]最短母串问题】

· · 题解

感谢@Duan2baka 的思路,感觉相当清晰,但是指针稍有不爽,于是就写了个数组版的.

主要思路:首先按照平常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;
}