字典树所有功能
1、在字典里查一个串
2、在字典里查含有该前缀的串的个数
3、
//放外面就是查整体
//放里头就是查外面
#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
int getnum(char x){
if(x>='A'&&x<='Z')
return x-'A';
else if(x>='a'&&x<='z')
return x-'a'+26;
else
return x-'0'+52;
}
void insert(char str[]){
int p=0,len=strlen(str);
for(int i=0;i<len;i++){
int c=getnum(str[i]);
if(!t[p][c])
t[p][c]=++idx;
p=t[p][c];
cnt[p]++;
//放外面就是搜整体
//放里头就是查前缀
}
//cnt[p]++;
}
int find(char str[]){
int p=0,len=strlen(str);
for(int i=0;i<len;i++){
int c=getnum(str[i]);
if(!t[p][c])
return 0;
p=t[p][c];
}
return cnt[p];
}
int main(){
scanf("%d",&T);
while(T--){
for(int i=0;i<=idx;i++)
for(int j=0;j<=122;j++)
t[i][j]=0;
for(int i=0;i<=idx;i++)
cnt[i]=0;
idx=0;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%s",s);
insert(s);
}
for(int i=1;i<=q;i++){
scanf("%s",s);
printf("%d\n",find(s));
}
}
//int n;
// scanf("%d",&n); // getchar();
// while(n--){
// char op[2];
// scanf("%s%s",op,s);
// if(*op=='I') insert(s);
// else cout<<find(s)<<endl;
// }
return 0;
}
标签:里查,int,char,&&,3000005,字典
From: https://www.cnblogs.com/yzzyang/p/18148965