2022春每日一题:Day 20

2022春每日一题:Day 20
2022春每日一题:Day 20

题目:Secret Message

老师说的trie树入门题
对于每个密码,存入trie树,每个字符对应编号i,则sum[i]++,最后结尾的编号为j,cnt[j]++
查询,每个字符对应编号为i,不存在直接返回ret,否则,ret+=cnt[i](某个密码是此查询的前缀),最后返回答案ret+sum[j]-cnt[j](cnt[j]已经加过一次,此查询是sum[j]个密码的前缀)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
const int N=5e5+5;
using namespace std;
int son[N<<1][2],cnt[N],n,m,a[N],tot,sum[N];
void insert(int len)
{
	int p=0;
	for(int i=1;i<=len;i++)
	{
		if(!son[p][a[i]])
		    son[p][a[i]]=++tot;
		p=son[p][a[i]];
		sum[p]++;
	}
	cnt[p]++;
}
int query(int len)
{
	int p=0,ret=0;
	for(int i=1;i<=len;i++)
	{
		if(!son[p][a[i]])
		    return ret;
		p=son[p][a[i]];
		ret+=cnt[p];
	}
	return ret+sum[p]-cnt[p];
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int len;
		scanf("%d",&len);
		for(int j=1;j<=len;j++)
		    scanf("%d",&a[j]);
		insert(len);
	}
	for(int i=1;i<=m;i++)
	{
		int len;
		scanf("%d",&len);
		for(int j=1;j<=len;j++)
		    scanf("%d",&a[j]);
		printf("%d\n",query(len));
	}
	return 0;
}
上一篇:GB28181码流抓包wireshark分析及提取码流


下一篇:hadoop系列之四:Hbase的安装与使用