字典树

· · 算法·理论

前言

字典树是一种树形结构，可用于处理字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。字典树上的每一个节点都代表一个字符串。空间 O(\sum|s|) 。

字典树还维护了所有字符串的前缀，这个性质非常有用。

正文

P8306 【模板】字典树

插入时，将字符串从前到后一个一个比较，如果没有该节点，则新建一个节点，每经过一个点，就将该节点的次数加一。

代码：

void insert(char a[]){
    int len=strlen(a+1),p=0; 
    f(i,1,len){
        int c=get(a[i]);
        if(!trie[p][c])
            trie[p][c]=++tot;
        p=trie[p][c];
        ++cnt[p];
    }
}

查询时，将字符串从前到后一个一个比较，如果没有该节点，返回 0 ，如果查找完毕，返回该节点次数。

代码：

int find(char a[]){
    int len=strlen(a+1),p=0;
    f(i,1,len){
        int c=get(a[i]);
        if(!trie[p][c])
            return 0;
        p=trie[p][c];
    }
    return cnt[p];
}

完整代码：

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define F(i,r,l) for(int i=r;i>=l;--i)
#define LL long long
#define ULL unsigned long long
#define read(n) {int _x=0,_ty=1;char _c=getchar();while(!isdigit(_c)){if(_c=='-')_ty=-1;_c=getchar();}while(isdigit(_c))_x=10*_x+_c-'0',_c=getchar();n=_x*_ty;}
using namespace std;
const int N=3000005,B=63;
int T,n,q,cnt[N],trie[N][B],tot;
char a[N];
inline int get(char c){
    return c>='A'&&c<='Z'?c-'A':(c>='a'&&c<='z'?c-'a'+26:c-'0'+52);
}
void insert(char a[]){
    int len=strlen(a+1),p=0; 
    f(i,1,len){
        int c=get(a[i]);
        if(!trie[p][c])
            trie[p][c]=++tot;
        p=trie[p][c];
        ++cnt[p];
    }
}
int find(char a[]){
    int len=strlen(a+1),p=0;
    f(i,1,len){
        int c=get(a[i]);
        if(!trie[p][c])
            return 0;
        p=trie[p][c];
    }
    return cnt[p];
}
int main(){
    read(T);
    while(T--){
        f(i,0,tot){
            f(j,0,62)
                trie[i][j]=0;
            cnt[i]=0;
        }
        tot=0;
        read(n);
        read(q);
        f(i,1,n){
            scanf("%s",a+1);
            insert(a);
        }
        f(i,1,q){
            scanf("%s",a+1);
            printf("%d\n",find(a));
        }
    }
    return 0;
}

扩展

0-1 Trie

0-1Trie

可持久化字典树

to be continued;

Trie 合并

to be continued;

Trie 分裂

to be continued;