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

#include
#define N 750
#define M 150000
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
int n,tot,edges,kk;
int Log[30],hd[N],to[N],nex[N],mark[N][5000],fa[M*10],C[M*10];
char str[N];
queueq;
struct Sta
{ int u,sta,id; Sta(int u&＃61;0,int sta&＃61;0,int id&＃61;0):u(u),sta(sta),id(id){}
};
queueQ;
struct Node
{int sta,f,tag,ch[27];
}t[N];
void add(int u,int v)
{nex[&＃43;&＃43;edges]&＃61;hd[u],hd[u]&＃61;edges,to[edges]&＃61;v;
}
void insert(int xx)
{ int p&＃61;0,i,j,len&＃61;strlen(str&＃43;1); for(i&＃61;1;i<&＃61;len;&＃43;&＃43;i) {int c&＃61;str[i]-&＃39;A&＃39;; if(!t[p].ch[c]) t[p].ch[c]&＃61;&＃43;&＃43;tot; p&＃61;t[p].ch[c]; } t[p].tag&＃61;1; t[p].sta|&＃61;Log[xx];
}
void build()
{ int i,j; for(i&＃61;0;i<27;&＃43;&＃43;i) if(t[0].ch[i]) q.push(t[0].ch[i]),add(0,t[0].ch[i]); for(;!q.empty();) {int u&＃61;q.front();q.pop(); for(i&＃61;0;i<27;&＃43;&＃43;i) {int qq&＃61;t[u].ch[i]; if(!qq) {t[u].ch[i]&＃61;t[t[u].f].ch[i]; continue; } t[qq].f&＃61;t[t[u].f].ch[i]; add(t[qq].f,qq); q.push(qq); }}
}
// 继承自己.
void dfs(int x)
{for(int i&＃61;hd[x];i;i&＃61;nex[i]) {int v&＃61;to[i]; t[v].sta|&＃61;t[x].sta; dfs(v); }
}
void print(int c)
{ if(C[c]&＃61;&＃61;-1) return; print(fa[c]); printf("%c",C[c]&＃43;&＃39;A&＃39;);
}
int main()
{ int i,j; scanf("%d",&n); for(i&＃61;1;i<&＃61;14;&＃43;&＃43;i) Log[i]&＃61;(1<<(i-1)); for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) scanf("%s",str&＃43;1),insert(i); build(),dfs(0),C[0]&＃61;-1; for(Q.push(Sta(0,0,kk)),mark[0][0]&＃61;1;!Q.empty();) {Sta e&＃61;Q.front(); Q.pop(); if(e.sta&＃61;&＃61;Log[n&＃43;1]-1) { print(e.id); return 0; } int v; int u&＃61;e.u; int idx&＃61;e.id; int sta&＃61;e.sta; for(i&＃61;0;i<27;&＃43;&＃43;i) { v&＃61;t[u].ch[i]; if(!v) continue; if(mark[v][sta|t[v].sta]) {continue; }&＃43;&＃43;kk; fa[kk]&＃61;idx; C[kk]&＃61;i; mark[v][sta|t[v].sta]&＃61;1; Q.push(Sta(v,(sta|t[v].sta),kk)); }}return 0;
}