2.数据结构：1.Tire 字符串统计

1.Tire 字符串统计

1. #include<algorithm>
2. #include<cstring>
3. #include<iostream>
5. using namespace std;
7. const int N=100010;
8. int son[N][26];//至多 N 层，每一层至多 26 个节点（字母）
9. int cnt[N];//字符串至多 N 个，标记每个字符串的最后一个字母，
10. //统计出现次数
11. int idx;//用到的节点的总数
12. char str[N];//单次输入的字符串
14. void insert(char str[]){
15.     int p=0;//根节点
16.     for(int i=0;str[i];i++){//字符串的每一个字母分别存在每一层
17.         int u=str[i]-'a';//把 a-z 映射到 0-25
18.         if(!son[p][u]){//假设该节点不存在
19.             son[p][u]=++idx;//把该节点构造出来
20.         }
21.         p=son[p][u];//走到下一层的节点
22.     }
23.     cnt[p]++;//标记字符串的最后一个字母，维护计数器
24. }
26. //查询和插入同理，不再赘述
27. int query(char str[]){
28.     int p=0;
29.     for(int i=0;str[i];i++){
30.         int u=str[i]-'a';
31.         if(!son[p][u]){
32.             return 0;
33.         }
34.         p=son[p][u];
35.     }
36.     return cnt[p];
37. }
39. int main(){
40.     int n;
41.     cin>>n;
42.    
43.     while(n--){
44.         char op[2];
45.         cin>>op>>str;
46.         if(op[0]=='I'){
47.             insert(str);
48.         }else{
49.             printf("%d\n",query(str));
50.         }
51.     }
52.    
53.     return 0;
54. }

复制代码