Description
Data Constraint
Solution
我们可以建出一颗trie，在trie上建广义后缀自动机sam，在sam上打好二进制标记，由于sam中fa[x]与x的关系是fa[x]的right集包含x的right集，所以我们可以将x的二进制与fa[x]or一下并更新答案，最后我们还可以发现一个二进制的答按肯定没有它的子集劣，O(2^N*N)下传一下即可，对于询问O(1)输出。
Code
using namespace std;
const int maxn=2e6+5;
struct code{
int len,a[26],fa,bz;
}f[maxn];
int n,m,i,t,j,k,q,nq,l,x,y,z,g[
maxn],p[
maxn],num,v[
maxn],b[
maxn],er[
21],bz[
maxn],g1[
maxn/2][
26],fa[maxn];
char s[maxn/10];
void insert(int np,int p,int x,int y){
f[np].len=f[p].len+1;f[np].bz=y;
while (!f[p].a[x] && p) f[p].a[x]=np,p=f[p].fa;
if (!p) f[np].fa=1;
else{q=f[p].a[x];
if (f[q].len==f[p].len+1) f[np].fa=q;
else{
nq=++num;f[nq]=f[q];f[q].fa=f[np].fa=nq;f[nq].len=f[p].len+1;
while (f[p].a[x]==q) f[p].a[x]=nq,p=f[p].fa;
}
}
}
void bfs(){
int i=0,j=1;
while (i<j){
x=v[++i];
for (k=0;k<26;k++){
y=g1[x][k];
if (!y) continue;
p[y]=++num,insert(p[y],p[x],k,bz[y]);v[++j]=y;
}
}
}
int main(){
freopen("wechat.in","r",stdin);freopen("wechat.out","w",stdout);
scanf("%d\n",&n);er[1]=1;
for (i=2;i<=n;i++)er[i]=er[i-1]*2;
for (i=1;i<=n;i++){
scanf("%s\n",s+1);t=strlen(s+1);x=0;
for (j=1;j<=t;j++){
if (s[j]=='<'){
x=fa[x];continue;
}
if (!g1[x][s[j]-97]) g1[x][s[j]-97]=++num,fa[num]=x;
x=g1[x][s[j]-97];bz[x]|=er[i];
}
}num=p[0]=1;
bfs();
for (i=1;i<=num;i++) b[f[i].len]++;
for (i=1;i<=num;i++) b[i]+=b[i-1];
for (i=1;i<=num;i++) v[b[f[i].len]--]=i;
for (i=num;i>=1;i--){
x=v[i];y=f[x].fa;f[y].bz=(f[x].bz|f[y].bz);
g[f[x].bz]=max(g[f[x].bz],f[x].len);
}q=(1<<n)-1;
for (i=q;i>=1;i--)
for (j=1;j<=n;j++)
if (er[j]&i)g[i-er[j]]=max(g[i-er[j]],g[i]);
scanf("%d\n",&m);
for (i=1;i<=m;i++){
scanf("%s\n",s+1);x=0;
for (j=1;j<=n;j++)
x+=er[j]*(s[j]-48);
printf("%d\n",g[x]);
}
}
