lg2922[水] 发表于 2018-04-23 | 分类于 算法 , 树 , Trie树 | 阅读数 次 链接:lg2922[水] 题解 简单Trie树,匹配路上的所有结束字符串都要加上,经过最后一个位置的字符串也要加上注意计算顺序就好… 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<cstdio> #include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define long longusing namespace std;const int N=5e5+7;int tr[N<<2][2],nm[N],sum[N<<2],n,m,cnt=1,end[N];inline void add(int *a,int len){ int p=1; rep(i,1,len){ if(!tr[p][a[i]])tr[p][a[i]]=++cnt; sum[tr[p][a[i]]]++;p=tr[p][a[i]]; } end[p]++;}inline int query(int *a,int len){ int p=1,ans=0; rep(i,1,len){ if(!tr[p][a[i]])return ans; p=tr[p][a[i]]; if(p)ans+=end[p]; } return ans+sum[p]-end[p];}int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d%d",&n,&m); rep(i,1,n){ int x;scanf("%d",&x); rep(j,1,x)scanf("%d",&nm[j]); add(nm,x); } rep(i,1,m){ int x;scanf("%d",&x); rep(j,1,x)scanf("%d",&nm[j]); printf("%d\n",query(nm,x)); } return 0;}