C++14(g++5.4) 解法, 执行用时: 168ms, 内存消耗: 2912K, 提交时间: 2019-12-09 18:55:59

#include<bits/stdc++.h>
using namespace std;


const int MAXN = 5e5 + 5;
struct Node {
  int val;
  int cnt;
  int ch[2];
};
int sz;
Node nodes[MAXN];

void insert(vector<int> A) {
  int cur = 0;
  for (auto a: A) {
    int &nxt = nodes[cur].ch[a];
    if (nxt == 0) nxt = ++sz;
    nodes[nxt].cnt++;
    cur = nxt;
  }
  nodes[cur].val++;
}

int query(vector<int> A) {
  int cur = 0;
  int cnt = 0;
  for (auto a: A) {
    int nxt = nodes[cur].ch[a];
    if (nxt == 0) return cnt;
    cur = nxt;
    cnt += nodes[cur].val;
  }
  // return cnt;
  return nodes[cur].cnt+cnt-nodes[cur].val;
}

int main() {
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  while (N--) {
    int n; cin >> n;
    vector<int> A(n); for (auto &a: A) cin >> a;
    insert(A);
  }
  while (M--) {
    int n; cin >> n;
    vector<int> A(n); for (auto &a: A) cin >> a;
    cout << query(A) << endl;
  }
}

C++ 解法, 执行用时: 179ms, 内存消耗: 2552K, 提交时间: 2021-12-05 19:57:10

#include<bits/stdc++.h>
using namespace std;
bool s[10001];
int trie[1000001][2],f[1000001],sum[1000001],tot;
int search(int &len,bool s[]){
	int ans = 0,t = 0,i = 0;
	for (;i < len;i++){
		t = trie[t][s[i]];
		if (!t)break;
		if (i != len - 1)
			ans += f[t];
	}
	if (i == len)ans += sum[t];
	return ans;
}
int main(){
	int n,m,a,t,i,*p;
	cin>>n>>m;
	while (n--){
		cin>>a;
		for (i = 0;i < a;i++)
			cin>>s[i];
		t = 0;
		for (i = 0;i < a;i++){
			p = &trie[t][s[i]];
			if (!*p)*p = ++tot;
			t = *p;
			sum[t]++;
		}
		f[t]++;
	}
	while (m--){
		cin>>a;
		for (i = 0;i < a;i++)
			cin>>s[i];
		cout<<search(a,s)<<endl;
	}
	return 0;
}