算法:trie树
题目理解
把加密信息看作一个集合,对每一条解密信息求:1.集合中哪些是它的前缀,2.它是集合中哪些加密信息的前缀。
因为这里每输入一个数字有空格,所以开个int类型数组来存储信息。
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=500000;
int tre[N][2],idx=1;
int cot[N],b[N];
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
while(n--)
{
int k;
scanf("%d",&k);
int a[k];
for(int i=0;i<k;i++)
scanf("%d",&a[i]);
int p=0;
for(int i=0;i<k;i++)
{
int u=a[i];
if(tre[p][u]==0)
tre[p][u]=idx++;
p=tre[p][u];
b[p]++;
}
cot[p]++;
}
while(m--)
{
int q;
scanf("%d",&q);
int c[q];
for(int i=0;i<q;i++)
scanf("%d",&c[i]);
int ans=0,p=0,flo=0;
for(int i=0;i<q;i++)
{
int u=c[i];
if(tre[p][u]==0)
{
flo=1;
break;
}
p=tre[p][u];
ans+=cot[p];
}
if(flo)
printf("%d\n",ans);
else
printf("%d\n",ans+b[p]-cot[p]);
}
return 0;
}