題目描述
貝茜正在領導奶牛們逃跑．為了聯(lián)絡乐纸，奶牛們互相發(fā)送秘密信息．
信息是二進制的衬廷，共有M(1≤M≤50000)條．反間諜能力很強的約翰已經(jīng)部分攔截了這些信息，知道了第i條二進制信息的前bi(l《bi≤10000)位．他同時知道汽绢，奶牛使用N(1≤N≤50000)條密碼．但是吗跋，他僅僅了解第J條密碼的前cj(1≤cj≤10000)位．
對于每條密碼J，他想知道有多少截得的信息能夠和它匹配．也就是說庶喜，有多少信息和這條密碼有著相同的前綴．當然小腊，這個前綴長度必須等于密碼和那條信息長度的較小者．
在輸入文件中，位的總數(shù)（即∑Bi+∑Ci）不會超過500000.
輸入輸出格式
輸入格式：
*第1行：兩個整數(shù)：M和N.
*行2..M + 1：行i + 1描述截取的代碼i久窟，其中包含整數(shù)b_i秩冈，后跟b_i空格分隔的0和1
*行M + 2..M + N + 1：行M + j + 1描述具有整數(shù)c_j的代碼字j，后跟c_j空格分隔的0和1
輸出格式：
*行1..M：行j：第j個代碼字可以匹配的消息數(shù)斥扛。
這道題用暴力并不好解決入问，而且數(shù)據(jù)量大，更是不可能稀颁。
下面介紹一個神奇的東西----trie樹
trie樹將信息存于邊芬失，以點相連，構成一棵樹匾灶，如圖所示棱烂；
從而判斷前綴時可以在原先建成的樹從樹根開始搜；
對于該題阶女，因為要統(tǒng)計前綴的數(shù)目颊糜，需要考慮該串是別的串的前綴的情況，還需要考慮別的串是該串的前綴的情況秃踩。 所以在建樹的時候需要記錄該節(jié)點的子樹上有多少個數(shù)串的結(jié)尾衬鱼，便于統(tǒng)計詢問的串是別的串的前綴的情況；同時在記錄該節(jié)點是多少個數(shù)串的結(jié)尾憔杨，以便于統(tǒng)記別的串是詢問的串的前綴的情況鸟赫；
那么就可以完美的完成這一題了；
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define INF 9999999
using namespace std;
struct Node{
int son[3],path,end;
}N[1000010];
int n,m,bi,cj,cnt=1,a[10010];
void insert(int a[]){
int now=1;
for(int i=1;i<=bi;i++){
if(N[now].son[a[i]]){N[now].path++; now=N[now].son[a[i]];}
else{N[now].path++; N[now].son[a[i]]=++cnt; now=cnt;} //子樹結(jié)尾數(shù)加一
}
N[now].end++;//結(jié)尾數(shù)加一
}
int count(int a[]){
int now=1,sum=0;
for(int i=1;i<=cj;i++){
if(!N[now].son[a[i]]) return sum;
else{
sum+=N[N[now].son[a[i]]].end;
now=N[now].son[a[i]];
}
}
return sum+N[now].path;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
scanf("%d",&bi);
for(int j=1;j<=bi;j++) scanf("%d",&a[j]);
insert(a);
}
for(int i=1;i<=n;i++){
scanf("%d",&cj);
for(int j=1;j<=cj;j++) scanf("%d",&a[j]);
int ans=count(a);
printf("%d\n",ans);
}
return 0;
}
點個關注給個贊謝謝啦Ｏ稹抛蚤！
