###### tags: `TanKhoa`

# Trie

## Trie là gì
là cấu trúc dữ liệu cây, gồm một nút gốc.
Mỗi nút có tối đa số con bằng số ký tự trong bảng chữ cái sử dụng


Mỗi xâu nạp vào trie tương ứng với một đường đi trên trie.

## Cài đặt

const int ALB = 26; // thông thường
struct Node{
    // end: bao nhiêu từ kết thúc tại đây
    // cnt: bao nhiêu từ đi ngang qua đây
    // p: ai là cha nó?
    int end, cnt, p;
    int child[ALB] = {};
    Node(){
        end = cnt = p = 0;
        memset(child, 0, sizeof(child));
    }
};
Node trie[MAX + 1]; 
int cntNode = 1;
const int root = 1;
void reset(){
    for (int i = 1; i <= cntNode; i++)
        trie[i] = Node();
    cntNode = 1;
    // gốc ở đỉnh 1 đã đươc khởi tạo lại.
}
void addString (string s){
    int node = root;
    trie[node].cnt++;
    for (char c: s){
        c -= 'a';
        if (trie[node].child[c] == 0){
            ++cntNode;
            trie[node].child[c] = cntNode;
            trie[cntNode].p = node;
        }
        node = trie[node].child[c];
        trie[node].cnt++;
    }
    trie[node].end++;
}
bool find(string s){
    int node = root;
    for (char c: s){
        c -= 'a';
        if (trie[node].child[c] == 0) return false;
        node = trie[node].child[c];
        if (trie[node].cnt == 0) return false;
    }
    return (trie[node].end == true)
}

## Set giới hạn bộ nhớ của cây Trie
Nguyên tắc: độ dài mảng $\geq$ tổng độ dài tối đa của tất cả các từ định thêm vào cây

## Phone Number
Với mỗi đỉnh tương ứng với số điện thoại, ta kiểm tra xem đỉnh đó có đỉnh con hay không. Nếu có, tức là số điện thoại này sẽ là tiền tố của một số nào đó khác, và khi đó không thỏa mãn đề.

// cài đặt trie, nhưng ALB = 10, và c = s[i] - '0';
bool check(string s){
    int node = root;
    for (int i = 0; i < s.length(); i++){
        char c = s[i] - '0';
        node = trie[node].child[c];
    }
    // chắc chắn trie[node].end == true
    // kiểm tra có con
    if (trie[node].cnt == 1)
        return true;
    else 
        return false;
    // for (int d = 0; d < ALB; d++)
    //     if (trie[node].child[d] != 0)
    //         return false;
    // return true;
}

string sdt[MAX + 1];

// với mỗi test, sau khi đọc đầu vào:
reset();
for (int i = 1; i <= n; i++)
    addString(sdt[i]);
bool oke = true;
for (int i = 1; i <= n; i++)
    if (check(sdt[i]) == false){
        oke = false; break;
    }
if (oke) cout << "YES\n"; else cout << "NO\n";

## Trie-Prefix
Vì ta chỉ xét các từ, nên ta chỉ quan tâm tới các node là kết thúc của một từ.

Với mỗi node như vậy, ta đếm xem có bao nhiêu cặp nhận xâu đại diện node đấy làm tiền tố.
Ta có hai thông tin $end, cnt$. Sau khi suy luận, ta thấy đáp án là $end(cnt-end) * C_{end}^2$.

## TrieADN
Thay vì chọn các xâu con, chúng ta sẽ chọn tiền tố chung, từ đó suy ra số xâu con nhận xâu đấy làm tiền tố.

Duyệt tất cả các node, với mỗi node lấy cnt * độ sâu, tìm max trong số các kết quả.

// dựng cây trie
long long answer = 0;
void dfs(int node, int depth){
    if (node == 0) return;
    long long coef = 1ll * depth * trie[node].cnt;
    answer = max(answer, coef);
    
    for (int i = 0; i < ALB; i++)
        dfs(trie[node].child[i], depth + 1);
}
for (int _ = 1; _ <= t; _++){
    reset();
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        string s; cin >> s;
        addString(s);
    }
    dfs(1, 0);
    cout << answer << '\n';
    answer = 0;
}

## Quản lý tập số trên trie
Coi mỗi số nguyên `int` là một xâu nhị phân 31 bit

const int ALB = 2;
const int BIGBIT = 30;
// struct Node như cũ, nhưng không cần end cho lắm.
const int root = 1;
Node trie[BIGBIT * MAX];
int cntNode = 0;

void addNum(int num){
    int node = root;
    trie[node].cnt++;
    for (int i = BIGBIT; i >= 0; i--){
        int bit = (num >> i) & 1; // lấy bit thứ i của số num
        if (trie[node].child[bit] == 0){
            ++cntNode;
            trie[node].child[bit] = cntNode;
            trie[cntNode].p = node;
        }
        node = trie[node].child[bit];
        trie[node].cnt++;
    }
    trie[node].end++;
}
int findNum(int num){ // trả về node chứa số, hoặc 0 nếu 0 tìm ra
    int node = root;
    for (int i = BIGBIT; i >= 0; i--){
        int bit = (num >> i) && 1;
        if (trie[node].child[bit] == 0)
            return false;
        node = trie[node].child[bit];
        if (trie[node].cnt == 0)
            return false;
    }
    return node;
}
void delNum(int num){
    if (findNum(num) == false) return;
    
    int node = root;
    trie[node].cnt--;
    for (int i = BIGBIT; i >= 0; i--){
        int bit = (num >> i) & 1;
        node = trie[node].child[bit];
        trie[node].cnt--;
    }
    trie[node].end--;
    // không cần thiết phải xóa đỉnh kể cả khi cnt = end = 0
}
int lower_bound(int x){ // có bao nhiêu số <= x
    int answer = 0;
    // tại một node nếu bit i = 1 thì toàn bộ số ở nhánh bit i = 0 đều nhỏ hơn
    int node = root;
    for (int i = BIGBIT; i >= 0; i--){
        int bit = (num >> i) & 1;
        if (bit == 1){
            int child += trie[node].child[0];
            if (child != 0)
                answer += trie[child].cnt;
        }
        
        if (trie[node].child[bit] == 0)
            return answer;
        node = trie[node].child[bit];
    }
    answer += trie[node].end;
    return answer;
}
int kthSmallest(int k){
    // điều kiện chạy: 1 <= k <= trie[root].cnt;
    // nếu nhánh 0 đủ số => sang nhánh 0
    // còn không thì trừ bớt k rồi sang nhánh 1
    int answer = 0;
    
    int node = root;
    for (int i = BIGBIT; i >= 0; i--){
        int bit;
        if (trie[node].child[0] == 0){
            bit = 1;
        } else {
            int c0 = trie[node].child[0];
            if (trie[c0].cnt >= k)
                bit = 0;
            else{
                k -= trie[c0].cnt;
                bit = 1;
            }
        }
        answer |= 1ll << bit;
        node = trie[node].child[bit];
    }
    return answer;
}

## TrieXOR
- Bước 1: dựng cây trie
- Bước 2: với mỗi số, duyệt bit từ vị trí 30 về 0:
- Nếu là bit 1, tìm bit 0 và ngược lại
- TH ví dụ: bit i = 1 => tìm 0. Nếu không có nhánh 0 thì quay lại tìm nhánh 1

int findXOR(int x){
    int answer = 0;
    
    int node = root;
    for (int i = BIGBIT; i >= 0; i--){
        int bitX = (x >> i) & 1;
        int bit = !bitX;
        if (trie[node].child[bit] == 0)
            bit = !bit;    // quay xe
        
        answer |= bit << i;    // chốt đáp án bit i
        node = trie[node].child[bit];
    }
    return answer;
}

// với mỗi test, sau khi nhập n và n số a_i
reset();
for (int i = 1; i <= n; i++)
    addNum(a[i]);
int answer = 0;
for (int i = 1; i <= n; i++){
    int so2 = findXOR(a[i]);
    answer = max(answer, a[i] ^ so2);
}
cout << answer;


## CSES1731

### Cày trâu

string s;
string dict[MAX];
int n, k;

// qhđ đếm từ 1, nên s = ' ' + s;

bool verify(int l, int r){
    string sub = s.substr(l, r-l+1);
    for (int i = 1; i <= k; i++)
        if (sub == dict[i]) return true;
    return false;
}

int f[MAX];
f[0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        f[i] += f[j-1] * verify(j, i) % MOD,
        f[i] %= MOD;

a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a