1.动态分配空间
const int N = 27; struct trie{ trie *Next[N]; int flag; trie(){ flag=1; memset(Next,NULL,sizeof(Next)); } }*root; void insert(string s){ int len=s.length(); trie *p=root,*q; for(int i=0;i<len;i++){ int id=s[i]-'a'; if(p->Next[id]==NULL){ q=new trie(); p->Next[id]=q; p=p->Next[id]; }else{ p=p->Next[id]; (p->flag)++; } } } int query(string s){ int len=s.length(); trie *p=root; for(int i=0;i<len;i++){ int id=s[i]-'a'; p=p->Next[id]; if(p==NULL)return 0; } return p->flag; } void free(trie *t){ if(t==NULL)return; for(int i=0;i<N;i++)if(t->Next[i])free(t->Next[i]); delete(t); }
2.静态空间
例题:洛谷P2580
const int N = 1e6+255; struct node{ bool rep; int son[30]; int num; }t[N]; int cnt=1,n,m; char s[105]; void insert(char *s){ int now=0; for(int i=0;s[i];i++){ int ch=s[i]-'a'; if(t[now].son[ch]==0)t[now].son[ch]=cnt++; now=t[now].son[ch]; t[now].num++; } } int find(char *s){ int now=0; for(int i=0;s[i];i++){ int ch=s[i]-'a'; if(t[now].son[ch]==0)return 3; now=t[now].son[ch]; } if(t[now].num==0)return 3; if(t[now].rep==0){ t[now].rep=1; return 1; } return 2; }
3.查询公共前缀的数量
void insert(char str[]){ int len=strlen(str),rt=0; for(int i=0;i<len;i++){ int cur=str[i]-'a'; if(trie[rt][cur]==0) trie[rt][cur]=++tot; rt=trie[rt][cur]; num[rt]++; } } int ask(char str[]){ int len=strlen(str),rt=0; for(int i 0;i<len;i++){ int cur=str[i]-'a'; if(trie[rt][cur]==0) return 0 ; rt=trie[rt][cur]; } return num[rt]; }
4.字符串排序(字典序)
void trie_sort(trie *root){ if(!root)return; if(root->flag){ cout<<root->s<<'\n'; return; } for(int i=0;i<26;i++)trie_sort(root->Next[i]); }
5.维护最长异或路径
例题:洛谷P4551
const int N = 2e6+255; struct edge{ int v,w,next; }e[N]; struct trie{ int s[5]; }t[N]; int head[N],cnt=-1,sum[N],tot,n; void add(int u,int v,int w){ e[++cnt].next=head[u]; e[cnt].v=v; e[cnt].w=w; head[u]=cnt; } void dfs(int x,int fa){ for(int i=head[x];~i;i=e[i].next){ int v=e[i].v,w=e[i].w; if(v!=fa){ sum[v]=sum[x]^w; dfs(v,x); } } } void build(int va,int x){ for(int i=(1<<30);i;i>>=1){ bool c=va&i; if(!t[x].s[c])t[x].s[c]=++tot; x=t[x].s[c]; } } int find(int va,int x){ int ans=0; for(int i=(1<<30);i;i>>=1){ bool c=va&i; if(t[x].s[!c]){ ans+=i; x=t[x].s[!c]; }else{ x=t[x].s[c]; } } return ans; } int main(){ memset(head,-1,sizeof(head));cnt=-1; cin>>n; for(int i=1,x,y,z;i<n;i++){ cin>>x>>y>>z; add(x,y,z); add(y,x,z); } dfs(1,-1); for(int i=1;i<=n;i++)build(sum[i],0); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,find(sum[i],0)); cout<<ans; return 0; }
6.维护异或和
const int N = 21; struct trie{ int ch[(N+1)*225][2],w[(N+1)*225],xorv[(N+1)*225],tot; int mknode(){ ++tot; ch[tot][1]=ch[tot][0]=w[tot]=xorv[tot]=0; return tot; } void maintain(int o){ w[o]=xorv[o]=0; if(ch[o][0]){ w[o]+=w[ch[o][0]]; xorv[o]^=xorv[ch[o][0]]<<1; } if(ch[o][1]){ w[o]+=w[ch[o][1]]; xorv[o]^=(xorv[ch[o][1]]<<1)|(w[ch[o][1]]&1); } w[o]&=1; } void inserts(int &o,int x,int dp){ if(!o)o=mknode(); if(dp>N)return (void)(w[o]++); inserts(ch[o][x&1],x>>1,dp+1); maintain(o); } void erase(int o,int x,int dp){ if(dp>20)return (void)(w[o]--); erase(ch[o][x&1],x>>1,dp+1); maintain(o); } void addall(int o){ swap(ch[o][0],ch[o][1]); if(ch[o][0])addall(ch[o][0]); maintain(o); } int merge(int a,int b){ if(!a)return b; if(!b)return a; w[a]+=w[b]; xorv[a]^=xorv[b]; ch[a][0]=merge(ch[a][0],ch[b][0]); ch[a][1]=merge(ch[a][1],ch[b][1]); return a; } }t;