登录
← 返回首页 | 代码片段 › 6 字符串 › 6.3 Trie › Trie / 搜索
JSON MD

6.3 Trie

Trie树 于是他错误的点名开始了
40 行
CPP JSON
【Trie树(于是他错误的点名开始了)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void add(char ch[]) — 加法更新 int find(char ch[]) — 查找(并查集寻根/二分查找)
C++ 39 行 CPP
#pragma once
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
const int SP=500003;
int trie[SP][26],pan[SP],ed[SP],re,t=1,n;
char ch[55];
inline void add(char ch[]){
    R a,i=0,p=1,m=strlen(ch);
    for(;i<m;i++){
        a=ch[i]-'a';
        if(!trie[p][a])trie[p][a]=++t;
        p=trie[p][a];
    }
    ed[p]=1;
}
inline int find(char ch[]){
    R re,i=0,p=1,m=strlen(ch);
    for(;i<m;i++){
        p=trie[p][ch[i]-'a'];
        if(!p)return 0;
    }
    re=ed[p];
    if(ed[p])ed[p]++;
    return re;
}
int main(){
    scanf("%d",&n);
    while(n--){scanf("%s",ch);add(ch);}
    scanf("%d",&n);
    while(n--){
        scanf("%s",ch);
        re=find(ch);
        if(!re)printf("WRONG\n");
        else if(re==1)printf("OK\n");
        else printf("REPEAT\n");
    }
}
Trie树 前缀统计
30 行
CPP JSON
【Trie树(前缀统计)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void add(char ch[]) — 加法更新 int find(char ch[]) — 查找(并查集寻根/二分查找)
C++ 29 行 CPP
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
const int SP=500003;
int trie[SP][26],pan[SP],ed[SP],re,t=1,n,m;char ch[55];
inline void add(char ch[]){
    R a,i=0,p=1,l=strlen(ch);
    for(;i<l;i++){
        a=ch[i]-'a';
        if(!trie[p][a])trie[p][a]=++t;
        p=trie[p][a];
    }
    ++ed[p];
}
inline int find(char ch[]){
    R i=0,p=1,ans=0,l=strlen(ch);
    for(;i<l;i++){
        p=trie[p][ch[i]-'a'];
        ans+=ed[p];
        if(!p)return ans;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    while(n--){scanf("%s",ch);add(ch);}
    while(m--){scanf("%s",ch);printf("%d\n",find(ch));}
}
可持久化Trie树 最大异或和
41 行
CPP JSON
【可持久化Trie树(最大异或和)】 Trie(字典树/前缀树)模板,高效存储和检索字符串集合。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re p,Re q,Re o,Re x) — 插入元素 int ask(Re p,Re q,Re o,Re x) — 核心算法函数 核心结构体:Trie 关键配置: N=6e5+5,logN=24 说明:freopen("123.txt","r",stdin);
C++ 40 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=6e5+5,logN=24;
int n,x,y,z,T,A[N],pt[N];char op;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Trie{
	int O,cnt[N*(logN+2)],tr[N*(logN+2)][2];
	inline void insert(Re p,Re q,Re o,Re x){
		if(o<0)return;Re i=(x>>o)&1;
		tr[p][i]=++O,tr[p][i^1]=tr[q][i^1];
		cnt[tr[p][i]]=cnt[tr[q][i]]+1;
		insert(tr[p][i],tr[q][i],o-1,x);
	}
	inline int ask(Re p,Re q,Re o,Re x){
		if(o<0)return 0;Re i=(x>>o)&1;
		if(cnt[tr[q][i^1]]>cnt[tr[p][i^1]])return (1<<o)+ask(tr[p][i^1],tr[q][i^1],o-1,x);
		else return ask(tr[p][i],tr[q][i],o-1,x);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(A[i]),A[i]^=A[i-1],T1.insert(pt[i]=++T1.O,pt[i-1],logN,A[i]);
	T1.insert(pt[0]=++T1.O,0,logN,0);
	while(T--){
		scanf(" %c",&op),in(x);
		if(op=='A')++n,A[n]=A[n-1]^x,T1.insert(pt[n]=++T1.O,pt[n-1],logN,A[n]);
		else in(y),in(z),--x,--y,printf("%d\n",T1.ask(x?pt[x-1]:0,pt[y],logN,z^A[n]));
	}
}
已复制