【题解】Secret Message G
题目描述
贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．
信息是二进制的，共有 M（1 \le M \le 50000）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 i 条二进制信息的前 b_i（1 \le b_i \le 10000）位，他同时知道，奶牛使用 N（1 \le N \le 50000）条暗号．但是，他仅仅知道第 j 条暗号的前 c_j（1 \le c_j \le 10000）位。
对于每条暗号 j，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。
在输入文件中，位的总数（即 \sum b_i + \sum c_i）不会超过 500000。
输入格式
第1行，两个整数 M 和 N。
第2...M+1行：每行一个整数 b_i，后跟 b_i 个整数1或0描述一条信息。
第M+2...M+N+1行：每行一个整数 c_j ，后跟c_j个整数1或0描述一条暗号。
输出格式
第1...M行：第j行输出能和第j条暗号匹配的信息数量。
输入输出样例
输入 #1
4 5
3 0 1 0
1 1
3 1 0 0
3 1 1 0
1 0
1 1
2 0 1
5 0 1 0 0 1
2 1 1 3
4 2 3 1 10 5 9 7输出 #1
1
3
1
1
2 分析
分析题意可知，题目给定M个二进制数组，依次给出一个二进制数组求这个二进制数组与给定的M个二进制数组拥有相同前缀的数量，可知算法核心为统计前缀，应使用Trie。
对给定的M个二进制数组进行建Trie，在建Trie经过的路径上的每一节点增加一个sum来表示经过这个节点的给定数组的数量，在每一个数组的末尾节点增加一个end来表示在这个节点结束的给定数组的数量。
查询前缀数量时有两种情况：
- 与数组有相同前缀的给定数组的长度均不大于数组长度：此时只需要统计查询路径上的end和，即可表示所有与数组有相同前缀的给定数组的数量。
- 有至少一个与数组有相同前缀的给定数组的长度大于数组长度：此时所有与数组有相同前缀的给定数组有两部分——小于数组长度和不小于数组长度的，此时所有与数组有相同前缀的给定数组的数量为查询路径上的end和减去数组末尾节点的end再加上减去数组末尾节点的sum。
代码
#include<bits/stdc++.h>
using namespace std;
int m,n,ans;
int len,a[10001];
int sum[500050],end[500050];
int node[500050][2];
int size=1,flag;
void insert(int cur,int dep){
if(dep>len){
end[cur]++;
return;
}
if(node[cur][a[dep]]==0){
node[cur][a[dep]]=++size;
sum[node[cur][a[dep]]]++;
insert(node[cur][a[dep]],dep+1);
}else{
sum[node[cur][a[dep]]]++;
insert(node[cur][a[dep]],dep+1);
}
}
void search(int cur,int dep){
if(dep>len){
printf("%d\n",ans-end[cur]+sum[cur]);
return;
}
cur=node[cur][a[dep]];
ans+=end[cur];
if(cur)search(cur,dep+1);
else{
printf("%d\n",ans);
return;
}
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
scanf("%d",&len);
for(int j=1;j<=len;j++){
scanf("%d",&a[j]);
}
insert(1,1);
}
for(int i=1;i<=n;i++){
scanf("%d",&len);
for(int j=1;j<=len;j++){
scanf("%d",&a[j]);
}
ans=0;
search(1,1);
}
return 0;
}最后修改：2021 年 07 月 03 日 07 : 40 PM
© 允许规范转载
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021 年 06 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
