trie樹總結和用法

trie樹（用法和總結）

- 南昌理工集訓隊

• 啥是trie樹（找張圖）

  
  - 這是trie樹的存盤基本原理，

  就是用樹狀形式儲存每一個字符，并保存節點，來進行的查找，
  這樣的做法是很高效的（可以看出，因為字符的重復利用率很高）

  - trie樹的作用

  1 儲存字符和查找字符（很高效，最基本的用法）
  2 求兩字符前后綴是否滿足字串（很重要，也是核心的用法）
  3 求前后綴有幾個相同的前綴或后綴
  4 異或對（難，我還沒學會，別問，問就是智商太低(；′⌒`) ）

    qwq 肯定很疑惑為什么不用KMP大法，（0.0）
  

  （當然也可以用KMP，但當數量很多很慢啊，要一個一個列舉，難過）

  - 模板提供

  重要環節到了 ，怎么用代碼實作？

• 第一個是儲存（插入trie樹）

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

• 第二個 查找字符

// 查詢字串
bool query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return false;
        p = son[p][u];
    }
    return cut[p];
}

這是主要的兩個打法，其余的都是自己去維護trie樹，

• 來一道模版題

#include<iostream>

using namespace std;
const int N=1e6+10;
int son[N][26],cut[N],idx;
string op,str;
void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]++;
}
int query(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cut[p];
}
int main(){
    int n;
    cin>>n;
    while(n--){
        cin>>op>>str;
        if(op=="I") insert(str);
        else cout<<query(str)<<endl;
    }
}

這就是trie樹高效存盤的用法，（一定要理解，不要死背，沒用）

• 比如再來一道簡單的模板題

• 代碼 （我們用repeat陣列來維護看看這個有沒有被點過，當然也可以直接用cut陣列 0-0）

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int son[N][26],cut[N],repeat[N],idx;
int n,m;
void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]++;
}
int query(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return p;
}
int main(){
    cin>>n;
    while(n--){
        string str;
        cin>>str;
        insert(str);
    }
    cin>>m;
    while(m--){
        string str;
        cin>>str;
        if(!query(str)) puts("WRONG");
        else if(cut[query(str)]&&!repeat[query(str)]++) puts("OK");
        else puts("REPEAT");
    }
}

對于初學者肯定有很多的疑惑，比如怎么維護大小寫和字母
用具體題目說話（一般可以直接開到58，就不需要特判，如果有數字就進行特判）

• 代碼（歸并排序算逆序對+trie樹儲存+cut陣列記錄位置）

// trie 樹+歸并排序
#include<iostream>
#include<string>
using namespace std;
const int N=5e5+10;
int son[N][58],cut[N],idx;
int n,a[N],b[N];
long long res=0;
void insert(string str,int k){
    int p=1;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'A';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]=k;
}
void query(string str,int k){
    int p=1;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'A';
        p=son[p][u];
    }
    a[k]=cut[p];
}
void merge_sort(int l,int r){
    if(l>=r) return ;
    int mid=l+r>>1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++],res+=mid-i+1;
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string str;
        cin>>str;
        insert(str,i);
    }
    for(int i=1;i<=n;i++){
        string str;
        cin>>str;
        query(str,i);
    }
    merge_sort(1,n);
    cout<<res;
    return 0;
}

來一道求前綴和的題

• 代碼（能力是不斷的刷題，來提高的）

我們用cut陣列來判斷是否滿足前綴
（提醒尋找時是 啊a.size()-1，不是a.size()）

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int N=1e5+10;
int son[N][10],cut[N],idx;
string str[N];
int T;
void init(){
    memset(son,0,sizeof(son));
    memset(cut,0,sizeof(cut));
    idx=0;
}
void insert(string a){
    int p=0;
    for(int i=0;i<a.size();i++){
        int u=a[i]-'0';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]++;
}
bool find(string a){
    int p=0;
    for(int i=0;i<a.size()-1;i++){
        int u=a[i]-'0';
        p=son[p][u];
        if(cut[p]) return true;
    }
    return false;
}
int main(){
    cin>>T;
    while(T--){
        init();
        int n;
        cin>>n;
        for(int i=0;i<n;i++) cin>>str[i],insert(str[i]);
        bool flag=false;
        for(int i=0;i<n;i++)
        if(find(str[i])){
            flag=true;
            break;
        }
        if(flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

最后來一道后綴題

當然這題很簡單N的范圍只有200，但是N范圍變大時，tried樹依舊可以解決 （主要是找不到題）

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int son[N][59],cut[N],idx;
int n,len;
void init(){
    memset(son,0,sizeof(son));
    memset(cut,0,sizeof(cut));
    idx=0;
    len=0;
}
void insert(string a){
    int p=0;
    for(int i=a.size()-1;i>=0;i--){
        int u=a[i]-'A';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
        cut[p]++;
    }
}
int query(string a){
    int p=0;
    for(int i=a.size()-1;i>=0;i--){
        int u=a[i]-'A';
        p=son[p][u];
        if(cut[p]==n) len++;
        else break;
    }
    return len;
}
int main(){
    while(cin>>n,n){
        init();
        string a,b;
        cin>>b;insert(b);
        for(int i=1;i<n;i++){
            cin>>a;insert(a); 
            if(a.size()<b.size()) b=a;
        }
        cout<<b.substr(b.size()-query(b))<<endl;
    }
    return 0;
}

題目是代碼修煉的核心，希望大家一起加油
萌新致敬ORZ ，點個贊唄（找題目，很辛苦的）
異或對學會了來補充，各位莫怪，能力有限，萌新磕頭，