```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define pb push_back
using namespace std;
int read()
{
int a = 0,x = 1;char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
return a*x;
}
const int N=2e5+7;
int n,m,id[N*5],ans1[N],ans2[N],vis2[N];
vector<int>s1[N],s2[N],g1[N],g2[N],s,g[N*5];
struct node{int len;map<int,int> ch;}d[N*5];
int fa[N],tot(1),las(1);
int add(int c)
{
int p = las,np = las = ++tot;
d[np].len = d[p].len + 1;
for(;p&&!d[p].ch[c];p = fa[p]) d[p].ch[c] = np;
if(!p) fa[np] = 1;
else {
int q = d[p].ch[c];
if(d[q].len == d[p].len + 1) fa[np] = q;
else {
int nq = ++tot;fa[nq] = fa[q],d[nq] = d[q];
d[nq].len = d[p].len + 1;
fa[q] = fa[np] = nq;
for(;p&&d[p].ch[c] == q;p = fa[p]) d[p].ch[c] = nq;
}
}
return np;
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n = read(),m = read();
for(int i = 1;i <= n;i ++) {
int x = read();las = 1;
for(int j = 0;j < x;j ++) {s1[i].pb(read());g1[i].pb(add(s1[i][j]));}
x = read(),las = 1;
for(int j = 0;j < x;j ++) {s2[i].pb(read());g2[i].pb(add(s2[i][j]));}
}
for(int i = 1;i <= m;i ++) {
int x = read();s.clear();
for(int j = 0;j < x;j ++) s.pb(read());
for(int j = 0,t = 1;j < x;j ++) {
t = d[t].ch[s[j]];
if(!t) break;
if(j == x-1) g[t].pb(i);
}
}
for(int i = 1;i <= n;i ++) {
for(int j = 0;j < s1[i].size();j ++) {
int t = g1[i][j];
while(t && id[t] != i) {
for(int k = 0;k < g[t].size();k ++)
if(vis2[g[t][k]] != i) ans2[g[t][k]] ++,vis2[g[t][k]] = i,ans1[i] ++;
id[t] = i;t = fa[t];
}
}
for(int j = 0;j < s2[i].size();j ++) {
int t = g2[i][j];
while(t && id[t] != i) {
for(int k = 0;k < g[t].size();k ++)
if(vis2[g[t][k]] != i) ans2[g[t][k]] ++,vis2[g[t][k]] = i,ans1[i] ++;
id[t] = i;t = fa[t];
}
}
}
for(int i = 1;i <= m;i ++) printf("%d\n",ans2[i]);
for(int i = 1;i <= n;i ++) printf("%d ",ans1[i]);
return 0;
}
```
by 忘怀星 @ 2021-03-29 16:16:23
复杂度假的吧。
by tommy0221 @ 2021-03-29 17:31:38