暴力做法

暴力过了，望周知。

建出AC自动机，得到fail指针。trie树直接用map存。但是我们并不用建AC自动机，通过朴素算法得到fail指针即可。

那么对于第一问，在fail树上做覆盖，若当前到了点 $u$，把 $u$ 到根的所有点加。但是这里要注意去重。

对于第二问，第一问的代码改一改即可。

关于复杂度，和老师讨论了一下，关于暴力跳fail树，这玩意很难卡，如果出题人太厉害了，大概最多卡到 $O(n \sqrt n)$。

代码（有debug版的）：

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N=1e5+5;
map<int,int> trie[N];
int n,m,fail[N],cnt[N],tot,res[N],ggg[N],wh[N];
bool flg[N];//遍历过的 
vector<int> a[N];
void build(){
	queue<int> q;int u,v;
	for (auto &p:trie[0]) q.emplace(p.second);
	while (!q.empty()){
		u=q.front();q.pop();
//		cout<<"in build : "<<u<<" "<<fail[u]<<"\n";
		for (auto &p:trie[u]){
			q.emplace(p.second);
//			cout<<"debuggggggggggggggg : "<<p.second<<"\n";
			for (v=fail[u];trie[v][p.first]==0 && v!=0;v=fail[v]);
			fail[p.second]=trie[v][p.first];
		}
	}
}
int modify(int t,bool f){//点到根的覆盖 
	int ans=0;
	for (;t!=114514 && flg[t]!=f;t=(t==0?114514:fail[t])) ans+=cnt[t],flg[t]=f,++ggg[t];
	return ans;
}
int jump(int u,int f){
	int v; 
	for (v=u;v!=114514 && trie[v][f]==0;v=(v==0?114514:fail[v]));
//	cout<<"\nin jump : "<<u<<" "<<f<<" "<<v<<"\n";
	if (v==114514) return 0;
	return trie[v][f];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i=1,l,t;i<=n;++i){
		cin >> l;for (int j=0;j<l;++j) cin >> t,a[i].emplace_back(t);
		a[i].emplace_back(N);
		cin >> l;for (int j=0;j<l;++j) cin >> t,a[i].emplace_back(t);
	}
	for (int i=1,l,t,u;i<=m;++i){
		cin >> l;u=0;
		for (int j=0;j<l;++j){
			cin >> t;
//			cout<<u<<"\n";
			if (!trie[u][t]) trie[u][t]=++tot;
			u=trie[u][t];
		}
		++cnt[u];wh[i]=u;
	}
//	for (int i=0;i<=tot;++i) for (auto &p:trie[i]) cout<<i<<" "<<p.second<<" "<<p.first<<"\n";
	build();
//	for (int i=0;i<=tot;++i) cout<<fail[i]<<" ";cout<<"\n";
	for (int i=1,u;i<=n;++i){
//		u=0;cout<<"about "<<i<<" : ";
		u=0;
		for (int j=0;j<a[i].size();++j) res[i]+=modify(u,1),u=jump(u,a[i][j]);res[i]+=modify(u,1);
//		cout<<"\n";
		u=0;
		for (int j=0;j<a[i].size();++j) modify(u,0),u=jump(u,a[i][j]);modify(u,0);
	}
	for (int i=1;i<=m;++i)
		cout<<ggg[wh[i]]/2<<"\n";
	for (int i=1;i<=n;++i) cout<<res[i]<<" ";
	return 0;
}
/*
3 10
10 0 2 2 3 3 2 0 1 3 0 6        2 0 0 3 3 3 
4 1 2 3 2                       7 0 0 2 1 1 2 2 
7 0 3 0 2 1 2 2                 7 3 1 2 0 0 3 3 

9            1 2 2 2 2 0 1 2 2 
10           1 0 0 1 0 0 3 1 2 3 
4            3 0 3 3 
1            2 
10           0 1 2 0 1 3 1 3 0 3 
10           2 3 0 2 1 1 3 2 1 1 
1            0 
10           2 0 0 1 1 1 1 0 2 2 
1            2 
2            2 2 


*/