acwing835Trie字符串统计,字典树（模板题）
字典树就是用树的方式记录单词，大幅度提高单词存储和查找的效率
我一开始想每个节点包括1个char和多个指针，然后每次遍历到该点时再遍历它的指针所指的字母，
然后发现下面这个视频里北大硕士的空间换时间妙：
他的做法：
因为只有26个英文字母，所以最多26个指针，且字母是有顺序的只要把下个字母-‘a’就可用o(1)复杂度知道是否存在该字母，字母在地址
设son【先字母地址】【下个字母】存下个字母的地址
板子：
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,son[N][26],cnt[N],idx;
//son[i][j]记录第i个字母的下个字母在第几号位置上,26个英语字母如下个是a就在0，cnt记入以这个结尾单词有几个
char str[N];
char op[5];
void Insert(char a[]){
int p=0;//指针
for(int i=0;str[i];i++){
int t=a[i]-'a';//下个字母
if(!son[p][t]) son[p][t]=idx++;
p=son[p][t]; //指针指向下个指针
}
cnt[p]++;//a[]单词字典树处理完毕，对应单词数+1
}
int Query(char a[]){
int p=0;
for(int i=0;str[i];i++){
int t=a[i]-'a';
if(!son[p][t]) return 0;//如果中途就没字母，直接返回0
p=son[p][t];
}
return cnt[p];//字典树中找到单词对应位置p，返回单词的cnt
}
int main(int argc, char** argv) {
cin>>n;
idx=1;
for(int i=0;i<n;i++){
scanf("%s",op);
scanf("%s",str);
if(op[0]=='I') Insert(str);
else cout<<Query(str)<<endl;
}
return 0;
} 
查看8道真题和解析
投递小米集团等公司10个岗位 >