Trie学习笔记

Trie(字典树)

基本数据结构

实际是:对于每个字符串组的每一个不同前缀建立节点

基本代码

void Insert(char *s,int p){ int now=0; int l=strlen(s); rep(i,0,l-1){ int k=s[i]-'a'; if(!nxt[now][k]) nxt[now][k]=++ncnt; now=nxt[now][k]; } }

不得不说,结构非常简单

但它有很多妙用

--->Xor Sum

典型数字trie

如何求出最大异或?

从最高位开始,能不同则不同,在建立的trie树上跑就行

const int N=100000,K=50; int n,m; int nxt[N*32][2]; int cnt; void Insert(int x){ int now=1; drep(i,31,0) { int y=(x&(1<<i))>0; if(!nxt[now][y]) nxt[now][y]=++cnt; now=nxt[now][y]; } } int Que(int x){ int now=1,ans=0; drep(i,31,0) { int y=(x&(1<<i))>0; if(nxt[now][!y]) ans|=(!y)<<i,now=nxt[now][!y]; else ans|=y<<i,now=nxt[now][y]; } return ans; } int main(){ rep(kase,1,rd()){ cnt=1; memset(nxt,0,sizeof nxt); n=rd(),m=rd(); rep(i,1,n) Insert(rd()); printf("Case #%d:\n",kase); rep(i,1,m) { int ans=Que(rd()); printf("%d\n",ans); } } }

转载于:https://www.cnblogs.com/chasedeath/p/11259334.html

相关资源：JAVA上百实例源码以及开源项目