踹樹（Trie 字典樹）

什麼都能上樹hhhhh

Trie 字典樹

~~ 比 KMP 簡單多了，無腦子選手學不會KMP，不會結論題~~

自己懶得造圖了OI WIKI 真棒

字典樹大概長這麼個亞子

嘔吼真棒

1. 就是将讀進去的字元串根據目前的字元是什麼和所處的位置構成一棵樹

2. 例如圖中\(1-->2-->5\)這一條路就是字元串\(aa\)那\(1-->4-->8-->13\)就是字元串\(cab\)

   貌似也沒有什麼東西的，題目的話基本就是套闆子，唯一奇怪的就是把一個數二級化建樹跑一些奇奇怪怪的東西

字元串:

struct Trie{
    int trie[][] ,Trie_num;
    void add(char *s){
        int now = 0 , 
        for(int i = 1 ; i <= len ;i++) {
            if(!trie[now][s[i]]) trie[now][s[i]] = +++Trie_num;
            now = trie[now][s[i]];
        }
    }
}
           

二進制：

struct Trie{
    int tire[][] ,Tire_num;
    void add(int x){
        int now = 0 , 
        for(int i = 31 ; i >= 0 ;i--) {
            int ch = (x>>(i)&1);
            if(!tire[now][ch]) tire[now][ch] = +++Trie
            now = tire[now][ch];
        }
    }
}
           

踹樹的時間複雜度其實不低普遍為\(\sum\limits_{i = 1}^{n}~|s_i|\)

例題

題目洛谷也有

這個題就是很顯然的闆子

• 詢問輸入字元串是否為已經輸入串的子串
• 直接邊建樹邊查詢就OK

建樹并查詢的時候會有2種情況

1. 一直沒有添加新的字母一直到該字元的最後一個,說明該字元串為已加入串的子串
2. 周遊到了某個字元串的最後一個字元，說明已經添加子串為該字元串的子串

然後就沒有然後了，你就把它切了(多測不清我是sb)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const int N = 1e6+100;
int read() {
    int s = 0 , f = 0 ; char ch = getchar() ;
    while(!isdigit(ch)) f |= (ch == '-') , ch = getchar();
    while(isdigit(ch)) s = s * 10 + (ch ^ 48) , ch = getchar();
    return f ? -s : s;
}
char s[20];
struct Trie{
    int Tir_num ,tir[N][11],vis[N];
    int add(char *s) {
        int len = strlen(s+1), now = 0;
        bool flag = 0;
        for(int i = 1 ; i <= len ;i++) {
            int ch = s[i]-'0';
            if(!tir[now][ch]) tir[now][ch] = ++Tir_num;
            else if(i == len) flag = 1;
            // cout << Tir_num<<" ";
            now = tir[now][ch];
            if(vis[now]) flag = 1;
            // cout <<now<<" "<< flag <<" ";
        }
        vis[now] = 1;
        // puts("");
        return flag;
    }
    void clear(){
        memset(tir,0,sizeof(tir));
        memset(vis,0,sizeof(vis));
        Tir_num = 0;
        // puts("LKP AK IOI");
    }
}tire;
int main() {
    int T = read() ;
    while(T--) {
        tire.clear();
        int n = read();
        int cnt = 0;
        for(int i = 1 ; i <= n;i++){
            scanf("%s", s+1);
            cnt += tire.add(s);
        }
       if(cnt) puts("NO");
       else puts("YES");
    }
    system("pause");
    return 0;
}
           

二進制的例題

• 根據\(xor\)的性質考慮貪心
• \(1\)^\(1\) \(=0~~\) \(0\) ^ \(1 = 1\) \(~~~~0\) ^ \(0 = 1\)

• 盡可能的讓二級制下的高位存在1

  那麼按照這個貪心思路

void query(int x) {
    int now = 0 , ans = 0;
    for(int i = 31 ; i >= 0 ;i-- ) {
        int ch = ((x >> i) & 1) , temp = ch ^ 1;
        if(tir[now][temp]) 
            now = tir[now][temp] ,
            ans = ((ans << 1) | 1);
        else {
            now = tir[now][ch];
            ans <<= 1;
        }
    }
    return ans;
}
           

還是貼一下完整代碼吧

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const int N = 4000010;
int read() {
    int s = 0 , f = 0 ; char ch = getchar() ;
    while(!isdigit(ch)) f |= (ch == '-') , ch = getchar();
    while(isdigit(ch)) s = s * 10 + (ch ^ 48) , ch = getchar();
    return f ? -s : s;
}
struct Trie{
    int  tire[N][2], Tir_num;
    void add(int x) {
        int now = 0 ;
        for(int i = 31 ; i >= 0 ;i--) {
            int ch = ((x>>i) & 1);
            if(!tire[now][ch]) tire[now][ch] = ++Tir_num;
            now = tire[now][ch];
        }
    }
    int query(int x){
        int now = 0 , ans = 0;
        for(int i = 31 ; i >= 0 ;i--) {
            int ch = ( (x >> i) & 1) , temp = ch ^ 1;
            if(tire[now][temp]) now = tire[now][temp],ans = (ans << 1) | 1;
            else now = tire[now][ch], ans <<= 1;
        }
        return ans;
    }
}tir;

int a[N];
int main() {
    int n = read();
    int ans = -1;
    for(int i = 1 ; i <= n ;i++) {
        a[i] = read(); 
        tir.add(a[i]);
        ans = max(ans,tir.query(a[i]));
    }
    printf("%d",ans);
    system("pause");
    return 0;
}
           

踹樹能做的AC自動機也能幹，好吧Tire樹AC自動機的一部分

自己說的僅僅是一部分，OI wiki講的很詳細，對題目分類講的也很詳細，覺得我寫的不好可以去OI wiki

Future never has to do with past time,but present time dose.