1.tire树

「tire数定义：」

什么是Trie树
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：

img

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

「变量介绍：」

1
2
3
C++
int arr[N][30], cnt[N], idx; // 二维数组 N 对应字符串最大长度，30对应 26个字的26种状态，这里稍微增大了点，无所谓
// 注意： idx 是一个每次插入新节点会自增的元素，目的是为了保证每一个节点是不同的，相当于有不同的编号。

「实现思路：」

tire树可以使用结构体或者二维数组存储，因为字符类型有固定的个数，使用二维数组较快，这里使用二维数组进行实现。

插入操作：遍历字符串，如果树中无此元素，则会创建一个新节点，并指向该新节点，有此元素则直接指向对应的子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
C++
void insertNUM(string s1)
{
    int p = 0;		// 默认树中有一个root根节点，但是为空，第一行全部是root的孩子节点，通过 u 来定位26个字母是否在孩子节点中
  	// 注意：arr[p][u] 当前这个节点（这个内存块） 代表着上一个节点是否存在这个孩子，而arr[p][u]里面的内容 代表他的编号，只要这个节点（孩子）存在，则必有一个编号，而且编号不重复。
  	// 在二维数组里面，可以理解为 每一行的每一个（列）都是上一个节点的孩子，每一行的行号代表着其父亲编号，每一列代表着其儿子的编号，例如 root 有 a b c 三个孩子，那么
  	// [0][0]  [0][1] [0][2]  就代表 root 节点的三个 a b c 孩子。
  	// !!!!! 那么加入 输入 acdf 这个字符串，对应的是什么呢？
  	// 因为根节点没有 a这个孩子，所以创建 [0][0]， 代表 a，idx = 1，[0][0] 里面的内容就是 1，代表着编号为1的节点（新创建的）
  	// 接下来  [1][2] 代表着 上一个 节点 a 有 c 这个孩子，但此时[1][2] 之前也不存在，内容为 ++idx为2 
  	// 再接下来 [2][3] 也不存在，新创建为 ++idx 为 3
  	// 在接下来 [3][5] 也不存在，新创建为 ++idx 为 4
  	// 此时循环结束，以 4 为结尾的单词的数量 +1，即cnt[p]++。
  	// !!!!! 再输入acdh
  	// 从根节点出发，有 [0][0] 存在，则让 p 指向 它的下一个节点，即 p = arr[p][u]
  	// 发现 [1][2] 也存在，继续 指向 它的下一个节点，即 p = arr[p][u]
  	// 发现 [2][3] 也存在 继续指向 它的下一个节点
  	// 发现 [3][7] 不存在，则创建新节点，编号为 ++idx 为 5
  	// 此时循环结束，以 5 为结尾的单词的数量 +1，即cnt[p]++。
  	// 循环结束
  	
    for(int i = 0; s1[i];i++)
    {
        int u = s1[i] - 'a';
        if(!arr[p][u]) arr[p][u] = ++idx;
        p = arr[p][u]; // arr里面的每一个位置，都是指向它的子节点的
    }

    cnt[p]++;
}

查询操作：从根节点出发，到结束为止，查询cnt[p]里面是否存在 以这个节点为结尾的数量，然后返回数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
C++
int query(string s1)
{
    int p = 0;
    for(int i = 0; s1[i];i++)
    {
        int u = s1[i] - 'a';
        if(!arr[p][u]) return 0;
        p = arr[p][u];
    }
    return cnt[p];
    
}

「完整代码：」

题目链接：835. Trie字符串统计 - AcWing题库

image-20240120141740542

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
C++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int arr[N][30], cnt[N], idx;

void insertNUM(string s1)
{
    int p = 0;
    for(int i = 0; s1[i];i++)
    {
        int u = s1[i] - 'a';
        if(!arr[p][u]) arr[p][u] = ++idx;
        p = arr[p][u]; // arr里面的每一个位置，都是指向它的子节点的
    }

    cnt[p]++;
}

int query(string s1)
{
    int p = 0;
    for(int i = 0; s1[i];i++)
    {
        int u = s1[i] - 'a';
        if(!arr[p][u]) return 0;
        p = arr[p][u];
    }
    return cnt[p];
    
}
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        char c1;
        cin >> c1;
        if (c1 == 'I')
        {
            string s1;
            cin >> s1;
            insertNUM(s1);
        } else {
            string s1;
            cin >> s1;
            int num = query(s1);
            cout << num << endl;
        }
    }

    return 0;
}

2. 最大异或对(难)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int arr[N];

int n;
int son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1; // 取出x 右移 i 位后的当前位
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (son[p][!u])
        {
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }

    return res;
}
int main()
{

    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    for (int i = 1; i <= n; i++)
    {
        insert(arr[i]);

        int t = query(arr[i]);

        res = max(res,arr[i] ^ t);
    }

    cout << res << endl; 
    return 0;
}