BZOJ1195[HNOI2006]最短母串——AC自动机+BFS+状态压缩

  1 #include<cmath>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 int n;
  9 int cnt;
 10 int num;
 11 char s[100];
 12 int t1[2460000];
 13 int t2[2460000];
 14 int end[605];
 15 int ans[605];
 16 int fail[1000];
 17 int a[605][26];
 18 int vis[605][4100];
 19 void build(char *s,int x)
 20 {
 21     int now=0;
 22     int len=strlen(s);
 23     for(int i=0;i<len;i++)
 24     {
 25         if(!a[now][s[i]-‘A‘])
 26         {
 27             a[now][s[i]-‘A‘]=++cnt;
 28         }
 29         now=a[now][s[i]-‘A‘];
 30     }
 31     end[now]|=(1<<x);
 32 }
 33 void getfail()
 34 {
 35     queue<int>q;
 36     for(int i=0;i<26;i++)
 37     {
 38         if(a[0][i])
 39         {
 40             fail[a[0][i]]=0;
 41             q.push(a[0][i]);
 42         }
 43     }
 44     while(!q.empty())
 45     {
 46         int now=q.front();
 47         q.pop();
 48         for(int i=0;i<26;i++)
 49         {
 50             if(a[now][i])
 51             {
 52                 fail[a[now][i]]=a[fail[now]][i];
 53                 end[a[now][i]]|=end[a[fail[now]][i]];
 54                 q.push(a[now][i]);
 55             }
 56             else
 57             {
 58                 a[now][i]=a[fail[now]][i];
 59             }
 60         }
 61     }
 62     return ;
 63 }
 64 void bfs()
 65 {
 66     queue<int>q1;
 67     queue<int>q2;
 68     q1.push(0);
 69     q2.push(0);
 70     int l=1;
 71     int r=1;
 72     while(l<=r)
 73     {
 74         int now=q1.front();
 75         int e=q2.front();
 76         q1.pop();
 77         q2.pop();
 78         if(e==((1<<n)-1))
 79         {
 80             for(;l>1;l=t2[l])
 81             {
 82                 ans[++num]=t1[l];
 83             }
 84             for(int i=num;i;i--)
 85             {
 86                 printf("%c",ans[i]+‘A‘);
 87             }
 88             return;
 89         }
 90         for(int i=0;i<26;i++)
 91         {
 92             if(!vis[a[now][i]][e|end[a[now][i]]])
 93             {
 94                 t1[++r]=i;
 95                 t2[r]=l;
 96                 q1.push(a[now][i]);
 97                 q2.push(e|end[a[now][i]]);
 98                 vis[a[now][i]][e|end[a[now][i]]]=1;
 99             }
100         }
101         l++;
102     }
103 }
104 int main()
105 {
106     scanf("%d",&n);
107     for(int i=0;i<n;i++)
108     {
109         scanf("%s",s);
110         build(s,i);
111     }
112     getfail();
113     bfs();
114     return 0;
115 }