字元串學習筆記二

4.0 四、字典樹

定義

字典樹又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和儲存大量的字元串（但不僅限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。它的優點是：利用字元串的公共字首來減少查詢時間，最大限度地減少無謂的字元串比較，查詢效率比哈希樹高。

實作

從百度百科瞟的圖

字典樹一般用一個二維數組定義，\(tr[now][t]\)表示\(now\)節點的字元為\(t\)的兒子的編号

同時我們還要開一個數組\(cnt[now][t]\)表示該節點的個數

在某些情況下，我們還要記錄有幾個字元串在該節點終結、該節點屬于第幾個字元串等等

一般來說，字典樹支援兩種操作：插入和查詢

假如要插入某個單詞

一開始我們位于根節點，也就是\(0\)号節點

接下來我們判斷根節點是否有某一個兒子\(ch\)

即\(tr[now][ch]\)是否等于\(0\)

如果等于\(0\)，那我們再新開一個節點，否則把該節點的個數加一

查詢操作也是如此，我們就從根節點一路走下去

如果可以走完，說明該單詞存在，否則該單詞不存在

代碼實作

以洛谷P2922為例

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+5;
char c[maxn];
int tr[maxn][3],cnt[maxn][3],tot,ed[maxn][3];
void ad(char s[]){
    int len=strlen(s);
    int now=0;
    for(int i=0;i<len;i++){
        int t=s[i]-'0';
        if(tr[now][t]){
            cnt[now][t]++;
        } else {
            tr[now][t]=++tot;
            cnt[now][t]=1;
        }
        if(i==len-1) ed[now][t]++;
        now=tr[now][t];
    }
}
int cx(char s[]){
    int len=strlen(s);
    int now=0,ans=0,js=0,jud=0,t;
    for(int i=0;i<len;i++){
        t=s[i]-'0';
        if(tr[now][t]){
            js+=ed[now][t];
            if(i!=len-1)now=tr[now][t];
        } else {
            jud=1;
            break;
        }
    }
    if(jud) return js;
    else return js-ed[now][t]+cnt[now][t];
}
char s[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        ad(s);
    }
    for(int i=1;i<=m;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        printf("%d\n",cx(s));
    }
    return 0;
}