Bzoj1195 [HNOI2006]最短母串 [AC自动机]

Time Limit: 10 Sec Memory Limit: 32 MB
Submit: 1304 Solved: 439

Description

给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。

Input

第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.

Output

只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

Sample Input

2
ABCD
BCDABC

Sample Output

ABCDABC

HINT

Source

暴力+状压：http://www.cnblogs.com/SilverNebula/p/6445487.html

AC自动机+BFS

这其实是我看到这题时最先有的思路，然而看到数据范围明显是为了状压设的，就写状压了。之后发现确实有AC自动机的解法，那么果断学习一发。

(其实也需要状压)先建好AC自动机，标记好每个结点对应的包含串状态，然后从根节点开始BFS(BFS保证串最短)，在每个状态从A到Z依次尝试扩展状态(保证字典序最小)

实际跑出来不比普通状压慢多少（大概是因为我的普通状压跑得太慢233）

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int mxn=;

 int L1[mxn*(<<)],L2[mxn*(<<)];

 queue<int>q1,q2;

 bool vis[mxn][(<<)];

 int n;

 int ans[mxn],num=;

 struct ACa{

     int t[mxn][];

     int fail[mxn];

     int end[mxn];

     int S,cnt;

     int q[],hd,tl;

     void init(){S=cnt=;memset(end,,sizeof end);return;}

     void insert(char *s,int id){

         int len=strlen(s),now=S;

         for(int i=;i<len;i++){

             if(!t[now][s[i]-'A'])t[now][s[i]-'A']=++cnt;

             now=t[now][s[i]-'A'];

         }

         end[now]|=(<<id);

     }

     void Build(){

         hd=;tl=;

         for(int i=;i<;i++)

             if(t[S][i]){q[++tl]=t[S][i];fail[t[S][i]]=S;}

             else t[S][i]=S;

         while(hd<=tl){

             int u=q[hd++];

             int v,r;

             for(int i=;i<;i++){

                 if(t[u][i]){

                     fail[t[u][i]]=t[fail[u]][i];

                     end[t[u][i]]|=end[t[fail[u]][i]];

                     q[++tl]=t[u][i];

                 }

                 else t[u][i]=t[fail[u]][i];

             }

         }

         return;

     }

     void solve(){

         hd=;tl=;int ed=(<<n)-;

         q1.push(S),q2.push();

         while(hd<=tl){

             int u=q1.front();q1.pop();

             int e=q2.front();q2.pop();

 //            printf("  e:%d\n",e);

             if(e==ed){//结束状态

                 for(;hd>;hd=L2[hd]){ans[++num]=L1[hd];}

                 for(int i=num;i;i--)printf("%c",ans[i]+'A');

                 return;

             }

             for(int i=;i<;i++){

                 if(!vis[t[u][i]][e|end[t[u][i]]]){

                     L1[++tl]=i;

                     L2[tl]=hd;

                     q1.push(t[u][i]);

                     q2.push(e|end[t[u][i]]);

                     vis[t[u][i]][e|end[t[u][i]]]=;

                 }

             }

             hd++;

         }

     }

 }ac;

 char s[];

 int main(){

     int i,j;

     scanf("%d",&n);

     ac.init();

     for(i=;i<n;i++)scanf("%s",s),ac.insert(s,i);

 //    for(i=1;i<=ac.cnt;i++)if(ac.end[i])printf("%d %d\n",i,ac.end[i]);

     ac.Build();

     ac.solve();

     return ;

 }

秒客网