BZOJ1195:[HNOI2006]最短母串 AC自动机+状压dp

思路:

首先我的思路十分傻叉,是\(f[i][j][k]\)表示长度为\(i\),在自动机上的节点为\(j\),包含子串的状态为\(k\)可不可能.但这样复杂度直接爆炸.

但是我们可以令\(f[i][j]\)表示在自动机上的节点为\(i\),包含子串的状态为\(j\)时的最短长度.

这样我们就转化成了边权均为1的单源最短路,BFS就行了.

若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.

(有点卡内存)

(话说我一开始AC自动机都写错,没治了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 12
#define L 610
 
short ch[L][26],end[L],pre[L],cnt;
 
char s[L];
 
int q[L],fr,ta;
short lastchar[L*(1<<N)];
int laststate[L*(1<<N)];
short state[L*(1<<N)];
short ins[L*(1<<N)];
bool vis[L][1<<N];
 
char ans[L];int id;
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int p,y;
    for(i=1;i<=n;++i){
        scanf("%s",s);int len=strlen(s);
        for(p=j=0;j<len;++j){
            if(!ch[p][y=s[j]-'A'])ch[p][y]=++cnt;p=ch[p][y];
        }end[p]|=1<<(i-1);
    }
    for(j=0;j<26;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<26;++j)if(ch[u][j]){
            for(q[ta++]=v=ch[u][j],r=pre[u];r&&!ch[r][j];r=pre[r]);end[v]|=end[pre[v]=ch[r][j]];
        }
        else ch[u][j]=ch[pre[u]][j];
    }
    int mask;
    for(fr=ta=0,state[0]=ins[0]=0,++ta;fr^ta;){
        u=ins[fr],mask=state[fr];
        if(mask==(1<<n)-1){
            for(;fr;fr=laststate[fr])ans[++id]=lastchar[fr];
            for(i=id;i>=1;--i)putchar('A'+ans[i]);
            return 0;
        }
        for(j=0;j<26;++j)if(!vis[ch[u][j]][mask|end[ch[u][j]]]){
            lastchar[ta]=j,laststate[ta]=fr,ins[ta]=ch[u][j],state[ta]=mask|end[ch[u][j]];
            vis[ins[ta]][state[ta]]=1;
            ta++;
        }++fr;
    }
    return 0;
}