Trie number dictionary tree

One 、 Preface

Dictionary tree is a magical thing . Imagine if we want to use a program to save some strings , But the same characters cannot be placed in different spaces , For example, there are two strings abc,abf, We found that ab It's the same , We need to store them in an array space ? How should we do it ？ Then there is why it is called a dictionary tree , In fact, it vividly illustrates his storage method , Is the dictionary . When we look up the dictionary , Will first look up the first letter of a word , Then continue to look up the following letters in the corresponding places . That is, we can use arrays to complete such storage

However, due to the limited space of general arrays , The dictionary tree will occupy a lot of space , One abc It takes up 3 Unit space , So you need to pay attention to the data range when using , Whether it can not explode space ！

Two 、 The relevant operation

① Pre variable definition

The dictionary tree needs a two-dimensional array space , be called son, Why is it so called . Because we use the root node of our whole tree idx=0 To express . This point is the head of the whole tree , He has countless sons , Sons have countless sons . So we affectionately call the subsequent node a son

and son The definition of is actually every x There will be corresponding y A son , Whether we are inserting or querying , In order to meet the requirement of not wasting extra space , We all need to make the first judgment , As a first x Whether your father already exists y This node , If it doesn't exist , Just give him a son , If there is , Just treat them equally as one son .

② Insert a string

Suppose the strings in our tree are all lowercase letters , Then our son can only have 26 individual , So when you open the array, you can open : int $son[N][26]$, And our later examples mainly focus on this .

I think the insertion is more clear , So just post a code

void insert(string ss) {
    int sz = ss.size();
    int p = 0;
    for(int i = 0; i < sz; i ++ ) {
        int u = ss[i] - 'a';
        // If you don't have this son, give him a son 
        if(son[p][u] == 0) son[p][u] = ++idx;
        // With or without a son ,p The pointer will go towards the son or the new point 
        // once p Go to the new point , In fact, it means that all the following points are new 
        p = son[p][u];
    }
}

③ Query a string

Query is actually similar to build , It depends on whether the string we want to query can completely complete the constructed string , As for inquiry , Combined with the following topics , You can understand , Directly post a small code .

int query(string ss) {
    int sz = ss.size();
    int p = 0;
    for(int i = 0; i < sz; i ++ ) {
        int u = ss[i] - 'a';
        if(son[p][u] == 0) return 0;
        p = son[p][u];
    }
    
    return cnt[p];
}

3、 ... and 、 Related topics

Topic 1

The above topic is a classic , Query the number of occurrences of the string , When we build trees , Let's open another cnt Array , This problem can be solved by recording how many letters appear in the position of the last letter of a string . You can take a direct look at the complete code .

complete AC Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;

int son[N][26], cnt[N], idx;

void insrt(string ss) {
    int sz = ss.size();
    int p = 0;
    for(int i = 0; i < sz; i ++ ){
        int u = ss[i] - 'a';
        if(son[p][u] == 0) son[p][u] = ++ idx;
        p = son[p][u];
    }
    
    cnt[p] ++ ;
}

int query(string ss) {
    int sz = ss.size();
    int p = 0;
    for(int i = 0; i < sz; i ++ ) {
        int u = ss[i] - 'a';
        if(son[p][u] == 0) return 0;
        p = son[p][u];
    }
    
    return cnt[p];
}

int main() {
    int n;
    cin >> n;
    while (n -- ) {
        string op, in;
        cin >> op >> in;
        
        if(op == "I") {
            insrt(in);
        }
        
        else {
            cout << query(in) << endl;
        }
    }
    return 0;
}

Topic two

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-kVxj0Ul6-1656845350472)(C:/Users/0604520/AppData/Roaming/Typora/typora-user-images/image-20220703165405990.png)]

This topic is more interesting , In fact, this topic is about a binary tree , Specific ideas are illustrated

We all know that a binary number XOR up , Same as 0, Different for 1, That's actually telling us again , We are constantly making achievements , You can use the element to be inserted , Compare with the elements in the tree , Every time I go to see if there is a son in the same position who is different from me , If any , We can forget that son's path and go .

For example, below ：

Insert... In turn 5,3,4 And find the element with the largest XOR ,

Insert again 4 When , First find the maximum XOR , We found that 4 The binary of is 100

about 1 This one , Look for it first 0 son , just 3 The first one in the world is 0, One analogy , He and 3 Or you can get the maximum XOR value 7(111);

complete AC Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100050, M = 31 * N;

// Because a son can only have 0,1 Two options 
int son[M][2], idx = 0;

void insert(int num) {
    int p = 0;
    // Weight is the most 31 position 
    for(int i = 30; i >= 0; i -- ) {
        int u = (num >> i) & 1;
        if(son[p][u] == 0) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int num) {
    int p = 0, ret = 0;
    for(int i = 30; i >= 0; i -- ) {
        int u = (num >> i) & 1;
        // If there are different sons 
        if(son[p][!u] != 0) {
            ret = ret * 2 + !u;
            p = son[p][!u];
        }
        // If there were no different sons 
        else {
            ret = ret * 2 + u;
            p = son[p][u];
        }
    }
    return ret;
}

int main() {
    int m, num;
    cin >> m;
    int ans = 0;
    while (m -- ) {
        cin >> num;
        insert(num);
        ans = max(num ^ query(num), ans);
    }
    
    cout << ans << endl;
    return 0;
}