trie树学习笔记&模板&例题

一、tire树

定义：Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。

实现：分为insert（插入），query（查询）操作。

二、

模板 acwingP835：https://www.acwing.com/problem/content/description/837/

插入操作：

void insert(char *str)
{
    int p = 0;  //类似指针，指向当前节点
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a'; //将字母转化为数字
        if(!son[p][u]) son[p][u] = ++idx;
        //该节点不存在，创建节点,其值为下一个节点位置
        p = son[p][u];  //使“p指针”指向下一个节点位置
    }
    cnt[p]++;  //结束时的标记，也是记录以此节点结束的字符串个数
}

查询操作：

int query(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u]; 
    }
    return cnt[p];  //返回字符串出现的次数
}

本题完整代码：

//一维是结点总数，而结点和结点之间的关系（谁是谁儿子）存在第二个维度
//比如[0][1]=3, [0]表示根节点，[1]表示它有一个儿子‘b’,这个儿子的下标是3；接着如果有一个[3][2]=8 ;
// 说明根节点的儿子‘b’也有一个儿子‘c’，这个孙子的下标就是8；
//这样传递下去，就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层，只能知道，它的儿子是谁
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int son[N][26],cnt[N],idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
void insert(char str[])
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		if(!son[p][u])son[p][u]=++idx;
		p=son[p][u];
	}

	cnt[p]++;
}
int query(char str[])
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		if(!son[p][u])return 0;
		p=son[p][u];
	}
	return cnt[p];
}
void solve()
{
	char op;
	char s[N];
	cin>>op>>s;
	if(op=='I')insert(s);
	else cout<<query(s)<<el;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t = 1;
	cin>>t;
	while(t--)
	  solve();
	return 0;
}

例题 （01字典树 求异或）acwingP143：https://www.acwing.com/problem/content/145/

思路：将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异。如果有异，就往这走，反之走能走的路。

代码（附带详细注释）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int son[N*31][2],idx;
int n,a[N];
void insert(int x)
{
  int p=0;
  dwn(i,30,0)
  {
    int u=x>>i&1;//取x的第i位二进制数是什么
    if(!son[p][u])son[p][u]=++idx;
    p=son[p][u];
  }
}
int search(int x)
{
  int p=0,res=0;
  dwn(i,30,0)//从最大位开始找
  {
    int u=x>>i&1;
    if(son[p][!u])//如果当前层有不同的数
    {
      p=son[p][!u];
      res=res*2+1;//*2相当于左移一位，如果找到对应位上有不同的数字，就再加一
      //感觉就是边转十进制边异或(不一样就+1)
    }
    else
    {
      p=son[p][u];
      res=res*2+0;//如果相同则*2即可
    }
  }
  return res;
}
void solve()
{
  cin>>n;
  rep(i,1,n)
  {
    cin>>a[i];
    insert(a[i]);//插入
  }
  int ans=0;
  rep(i,1,n)
    ans=max(ans,search(a[i]));//找到最大异或值
  cout<<ans<<el;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--)
      solve();
    return 0;
}