NO.81十六届蓝桥杯备战|数据结构-Trie树-字典树-前缀树|于是他错误的点名开始了|最大异或对 The XOR Largest Pair(C++)

1. 字典树的概念
   Trie树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。
   我们可以把字典树想象成⼀棵多叉树，每⼀条边代表⼀个字符，从根节点到某个节点的路径就代表了⼀个字符串。例如，要存储 “abc” 、 “abd” 、 “acde” 以及 “cd” 时，构建的字典树如下
   

2. 字典树的作⽤
   当我们在字典树的每⼀个结点位置，额外维护⼀些信息时，就可以做到很多事情：

• 查询某个单词是否出现过，并且出现⼏次；
• 查询有多少个单词是以某个字符串为前缀；
• 查询所有以某个前缀开头的单词；（这个作⽤可以⽤到输⼊法中，输⼊拼⾳的时候，可以提⽰可能的单词）
  当然，除了上述作⽤以外，字典树还可以解决别的问题，后续可以在做题中体会

3. 字典树的实现
   实现⼀个能够查询单词出现次数以及查询有多少个单词是以某个字符串为前缀的字典树，默认全是⼩写字⺟。

准备⼯作：

#include <iostream>  
#include <cstring>  
using namespace std;  
const int N = 1e6 + 10;  //表示所有的字符串中一共有多少个字符
int tree[N][26], p[N], e[N];
int idx;

tree：二维数组，第一维表示字符串中一共有多少个字符，第二维表示字符里的规模，全是小写字母的话就是26
tree[i]：表示i号节点的孩子信息
tree[i][0]：表示‘a’的路径信息
tree[i][1]：表示‘b’的路径信息
tree[i][3]：表示‘c’的路径信息
p[i]：表示i号节点的pass信息
e[i]：表示i号节点的end信息
idx：新来一个字符之后，为它分配位置

插⼊字符串：

void insert(string& s)  
{  
	int cur = 0; // 从根结点开始  
	p[cur]++; // 这个格⼦经过⼀次  
	for(auto ch : s)  
	{  
		int path = ch - 'a';  
		// 如果没有路  
		if(tree[cur][path] == 0) tree[cur][path] = ++idx;  
		cur = tree[cur][path];  
		p[cur]++;  
	}  
	e[cur]++;  
}

查询字符串出现的次数

int find(string& s)  
{  
	int cur = 0;  
	for(auto ch : s)  
	{  
		int path = ch - 'a';  
		if(tree[cur][path] == 0) return 0;  
		cur = tree[cur][path];  
	}  
	return e[cur];  
}

查询有多少个单词以字符串 s 为前缀

int find_pre(string& s)
{  
	int cur = 0;  
	for(auto ch : s)  
	{  
		int path = get_num(ch);  
		if(tree[cur][path] == 0) return 0;  
		cur = tree[cur][path];  
	}  
	return p[cur];  
}

P8306 【模板】字典树 - 洛谷

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 10;

int n, q;
int tr[N][62], p[N];
int idx;

int get_num(char ch)
{
    if (ch >= 'a' && ch <= 'z') return ch - 'a';
    else if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 26;
    else return ch - '0' + 52;
}

void insert(string& s)
{
    int cur = 0;
    p[cur]++;

    for (auto ch : s)
    {
        int path = get_num(ch);
        if (tr[cur][path] == 0) tr[cur][path] = ++idx;

        cur = tr[cur][path];
        p[cur]++;
    }
}

int find_pre(string& s)
{
    int cur = 0;

    for (auto ch : s)
    {
        int path = get_num(ch);
        if (tr[cur][path] == 0) return 0;

        cur = tr[cur][path];
    }
    return p[cur];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;

    while (T--)
    {
        //初始化
        //memset(tr, 0, sizeof tr);
        //memset(p, 0, sizeof p);
        for (int i = 0; i <= idx; i++)
        {
            for (int j = 0; j < 62; j++)
            {
                tr[i][j] = 0;        
            }
        }
        for (int i = 0; i <= idx; i++) p[i] = 0;
        
        idx = 0;
        
        cin >> n >> q;        
        while (n--)
        {
            string s; cin >> s;
            insert(s);
        }
        while (q--)
        {
            string s; cin >> s;
            cout << find_pre(s) << endl;
        }
    }
    
    return 0;
}

P2580 于是他错误的点名开始了 - 洛谷

⽤字典树维护字符串，当查询之后，将e数组修改成-1即可

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int n, m;
int tr[N][26], e[N];
int idx;

void insert(string& s)
{
    int cur = 0;
    
    for (auto ch : s)
    {
        int path = ch - 'a';
        if (tr[cur][path] == 0) tr[cur][path] = ++idx;
        cur = tr[cur][path];
    }
    e[cur]++;
}

int find(string &s)
{
    int cur = 0;
    
    for (auto ch : s)
    {
        int path = ch - 'a';
        if (tr[cur][path] == 0) return 0;
        cur = tr[cur][path];
    }
    if (e[cur] > 0)
    {
        e[cur] = -1;
        return 1;
    }
    return e[cur];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    while (n--)
    {
        string s; cin >> s;
        insert(s);
    }
    cin >> m;
    while (m--)
    {
        string s; cin >> s;
        int ret = find(s);
        if (ret == 0) cout << "WRONG" << endl;
        else if (ret == 1) cout << "OK" << endl;
        else cout << "REPEAT" << endl;
    }
    
    return 0;
}

P10471 最大异或对 The XOR Largest Pair - 洛谷

将所有数按照⼆进制位存在字典树中，针对每⼀个数x ，按照⼆进制匹配最优的⽅案

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

int tr[N * 32][2], idx;

void insert(int x)
{
    int cur = 0;

    for (int i = 31; i >= 0; i--)
    {
        int path = ((x >> i) & 1);
        if (tr[cur][path] == 0) tr[cur][path] = ++idx;
        cur = tr[cur][path];
    }
}

int find(int x)
{
    int cur = 0;
    int ret = 0;
    for (int i = 31; i >= 0; i--)
    {
        int path = ((x >> i) & 1);
        //贪心，要去相反的路
        if (tr[cur][path^1])
        {
            ret |= (1 << i);
            cur = tr[cur][path^1];
        }
        else
        {
            cur = tr[cur][path];
        }
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        insert(a[i]);
    }

    int ret = 0;
    for (int i = 1; i <= n; i++)
    {
        ret = max(ret, find(a[i]));        
    }

    cout << ret << endl;
    
    return 0;
}