数据结构--Trie树

Trie树查找和插入的时间复杂度均为O(n)。

https://www.acwing.com/problem/content/837/

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1e5+10;//输入字符串的总长度为1e5+10
 4 int son[N][26],cnt[N],idx;//son[i]表示字符串第i个字符是什么，cnt[i]表示字符以第i个字符结尾的字符串有多少个
 5 char s[N];
 6 void insert(char s[]){
 7     int p=0;
 8     for(int i=0;s[i];i++){
 9         int u=s[i]-'a';
10         if(!son[p][u]){
11             son[p][u]=++idx;
12         }
13         p=son[p][u];
14     }
15     cnt[p]++;
16 }
17 int query(char s[]){
18     int p=0;
19     for(int i=0;s[i];i++){
20         int u=s[i]-'a';
21         if(!son[p][u]){
22             return 0;
23         }
24         p=son[p][u];
25     }
26     return cnt[p];
27 }
28 int main(void){
29     int n;
30     cin>>n;
31     for(int i=0;i<n;i++){
32         char op[2];
33         cin>>op>>s;
34         if(op[0]=='I'){
35             insert(s);
36         }else{
37             cout<<query(s)<<endl;
38         }
39     }
40     return 0;
41 }

https://www.acwing.com/problem/content/145/

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1e5+10,M=N*31;
 4 int a[N];
 5 int son[M][2],idx;
 6 void insert(int x){
 7     int p=0;
 8     for(int i=30;i>=0;i--){
 9         int u=(x>>i)&1;
10         if(!son[p][u]) son[p][u]=++idx;
11         p=son[p][u];
12     }
13 }
14 int query(int x){
15     int p=0;
16     int res=0;
17     for(int i=30;i>=0;i--){
18         int u=(x>>i)&1;
19         if(son[p][!u]) p=son[p][!u],res+=1<<i;
20         else p=son[p][u];
21     }
22     return res;
23 }
24 int main(void){
25     int n;
26     cin>>n;
27     for(int i=0;i<n;i++){
28         cin>>a[i];
29         insert(a[i]);
30     }
31     int res=0;
32     for(int i=0;i<n;i++){
33         res=max(res,query(a[i]));
34     }
35     cout<<res;
36     return 0;
37 }