题目: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;
}