题目：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;

}

巴特西

2022春每日一题：Day 20

题目：Secret Message

最新文章

热门文章