题目描述
贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．
信息是二进制的，共有M(1≤M≤50000)条．反间谍能力很强的约翰已经部分拦截了这些信息，知道了第i条二进制信息的前bi(l《bi≤10000)位．他同时知道，奶牛使用N(1≤N≤50000)条密码．但是，他仅仅了解第J条密码的前cj(1≤cj≤10000)位．
对于每条密码J，他想知道有多少截得的信息能够和它匹配．也就是说，有多少信息和这条密码有着相同的前缀．当然，这个前缀长度必须等于密码和那条信息长度的较小者．
在输入文件中，位的总数（即∑Bi+∑Ci）不会超过500000.
输入输出格式
输入格式：
*第1行：两个整数：M和N.
*行2..M + 1：行i + 1描述截取的代码i，其中包含整数b_i，后跟b_i空格分隔的0和1
*行M + 2..M + N + 1：行M + j + 1描述具有整数c_j的代码字j，后跟c_j空格分隔的0和1
输出格式：
*行1..M：行j：第j个代码字可以匹配的消息数。
这道题用暴力并不好解决，而且数据量大，更是不可能。
下面介绍一个神奇的东西----trie树
image.png
trie树将信息存于边，以点相连，构成一棵树，如图所示；
从而判断前缀时可以在原先建成的树从树根开始搜；
对于该题，因为要统计前缀的数目，需要考虑该串是别的串的前缀的情况，还需要考虑别的串是该串的前缀的情况。 所以在建树的时候需要记录该节点的子树上有多少个数串的结尾，便于统计询问的串是别的串的前缀的情况；同时在记录该节点是多少个数串的结尾，以便于统记别的串是询问的串的前缀的情况；
那么就可以完美的完成这一题了；
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define INF 9999999
using namespace std;
struct Node{
int son[3],path,end;
}N[1000010];
int n,m,bi,cj,cnt=1,a[10010];
void insert(int a[]){
int now=1;
for(int i=1;i<=bi;i++){
if(N[now].son[a[i]]){N[now].path++; now=N[now].son[a[i]];}
else{N[now].path++; N[now].son[a[i]]=++cnt; now=cnt;} //子树结尾数加一
}
N[now].end++;//结尾数加一
}
int count(int a[]){
int now=1,sum=0;
for(int i=1;i<=cj;i++){
if(!N[now].son[a[i]]) return sum;
else{
sum+=N[N[now].son[a[i]]].end;
now=N[now].son[a[i]];
}
}
return sum+N[now].path;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
scanf("%d",&bi);
for(int j=1;j<=bi;j++) scanf("%d",&a[j]);
insert(a);
}
for(int i=1;i<=n;i++){
scanf("%d",&cj);
for(int j=1;j<=cj;j++) scanf("%d",&a[j]);
int ans=count(a);
printf("%d\n",ans);
}
return 0;
}
点个关注给个赞谢谢啦！！
