BZOJ1195:[HNOI2006]最短母串 AC自动机+状压dp
思路:
首先我的思路十分傻叉,是f[i][j][k]表示长度为i,在自动机上的节点为j,包含子串的状态为k可不可能.但这样复杂度直接爆炸.
但是我们可以令f[i][j]表示在自动机上的节点为i,包含子串的状态为j时的最短长度.
这样我们就转化成了边权均为1的单源最短路,BFS就行了.
若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.
(有点卡内存)
(话说我一开始AC自动机都写错,没治了
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #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;} |
评论 (0)