【题意概述】
给出n个01串组成的字典和m个询问，每次询问某个01串和多少个字典中的串有相同的前缀。（前缀长度是两串中较小的部分）
【题解】
直接上Trie树即可。树上每个节点记录两个信息：这个节点有多少个串经过，这个节点是多少个串的结尾。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define LL long long 5 #define rg register 6 #define N 500010 7 using namespace std; 8 int n,m,a[N][4],now,ans,tot; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 int main(){ 16 memset(a,0,sizeof(a)); 17 n=read(); m=read(); 18 for(rg int i=1;i<=n;i++){ 19 int x=read(); now=0; 20 while(x--){ 21 int y=read(); 22 if(a[now][y]>0) now=a[now][y]; 23 else a[now][y]=++tot,now=a[now][y]; 24 a[now][2]++; 25 } 26 a[now][3]++; 27 } 28 while(m--){ 29 int x=read(); bool ok=1; ans=now=0; 30 while(x--){ 31 int y=read(); 32 if(a[now][y]&&ok){ 33 now=a[now][y]; 34 if(a[now][3]) ans+=a[now][3]; 35 } 36 else ok=0; 37 } 38 if(ok) ans+=a[now][2]-a[now][3]; 39 printf("%d\n",ans); 40 } 41 return 0; 42 } View Code
转载于:https://www.cnblogs.com/DriverLao/p/9461638.html
相关资源：数据结构—成绩单生成器