字典树（trie树） luoguP2922

题目描述

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．

信息是二进制的，共有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;
}

点个关注给个赞谢谢啦！！