Description
题意就是，给你n个字符串，然后给你一些二进制，然后求二进制为1的位置他们的最长公共子串。
Solution
这就是一道SAM的裸题。 构出一颗trie，然后trie上建SAM（要用bfs来建），然后每个节点标记一个二进制，最后每个fail树上的父亲把儿子的标记全部or起来。 然后把这个二进制状态更新到子集上，如果
3n
枚举子集会超时，随意要1位位的往下转移
2nn
Code
using namespace std;
const
int maxn=
1e6+
7;
int i,j,k,l,n,
m,ans,len,tot,
x,op;
int num,a[maxn],f[maxn];
int p,np,
q,nq,w[maxn
*3],er[
21],b[maxn
*3],c[maxn
*3],da,e[maxn
*3];
int d[maxn
*2];
int tr[maxn
*2][
26];
char
s[maxn],st[maxn];
struct node{
int fa,len,son[
26],w;
}t[maxn
*2];
int extend(
int x,
int last,
int u){
t[np=++num].len=t[p=
last].len+
1;t[np].w=u;
while(p&&!t[p].son[
x])t[p].son[
x]=np,p=t[p].fa;
if(!p)t[np].fa=
1;
else{
q=t[p].son[
x];
if(t[
q].len==t[p].len+
1)t[np].fa=
q;
else{
t[nq=++num]=t[
q];t[nq].w=u;
t[nq].len=t[p].len+
1;
t[
q].fa=t[np].fa=nq;
while(p&&t[p].son[
x]==
q)t[p].son[
x]=nq,p=t[p].fa;
}
}
return np;
}
void bfs(){
int i,j,k,
x,
y;w[d[
1]=
0]=
1;
//w[
1]=extend(a[
1],d[
1]=
1);
for(i=j=
1;i<=j;i++){
x=d[i];
fo(k,
0,
25){
y=
tr[
x][k];
if(!
y)
continue;
w[d[++j]=
y]=extend(k,w[
x],b[
y]);
}
}
}
int main(){
freopen(
"wechat.in",
"r",stdin);
freopen(
"wechat.out",
"w",stdout);
er[
0]=
1;fo(i,
1,
20)er[i]=er[i-
1]
*2;
scanf(
"%d",&n);tot=
1;
fo(i,
1,n){
scanf(
"%s",st+
1);len=strlen(st+
1);
m=
0;da=max(da,len);st[++len]=
'<';
fo(j,
1,len)
if(st[j]==
'<'){
if(st[j-
1]!=
'<'){
x=
0;
fo(k,
1,
m){
if(d[k])
x=d[k];
else{
if(!
tr[
x][
s[k]-
'a'])
tr[
x][
s[k]-
'a']=++op;
x=
tr[
x][
s[k]-
'a'];b[
x]|=er[i-
1];
}
d[k]=
x;
}
}
d[
m]=
0;--
m;
}
else s[++
m]=st[j],d[
m]=
0;
fo(j,
1,len)d[j]=
0;
}
num=
1;
bfs();
fo(i,
1,num)c[t[i].len]++;
fo(i,
1,da)c[i]+=c[i-
1];
fod(i,num,
1)e[c[t[i].len]--]=i;
fod(i,num,
1)
x=e[i],t[t[
x].fa].w|=t[
x].w;
fo(i,
1,num)
x=e[i],f[t[
x].w]=(f[t[
x].w]<t[
x].len)?t[
x].len:f[t[
x].w];
fod(i,er[n]-
1,
1){
fo(j,
1,n){
if(i&er[j-
1])f[i-er[j-
1]]=(f[i-er[j-
1]]<f[i])?f[i]:f[i-er[j-
1]];
}
}
for(scanf(
"%d",&
m);
m;
m--){
scanf(
"%s",
s+
1);k=
0;
fo(i,
1,n)
if(
s[i]==
'1')k+=er[i-
1];
printf(
"%d\n",f[k]);
}
}
