Trie字典树

Trie树的实现方法与性质

Trie树 （字典树）可以高效统计、排序、保存大量字符串

代码实现：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int idx = 0, cnt[N], son[N][26]; 

char str[N];

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]++;                      //cnt记录该串出现的次数
}

void query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
        {
            cout << 0 <<endl;
            return;
        }
        p = son[p][u];
    }
    cout << cnt[p] <<endl;
    return;
}

int main()
{
    int m;
    scanf("%d", &m);
    while (m--)
    {
        char a[2];
        scanf("%s%s", a, str);
        if (a[0] == 'I')
        {
            insert(str);
        }
        else
        {
            query(str);
        }
    }
    return 0;
}

性质：

• 根节点没有字符，除根节点外的所有节点只保存一个字符
• 从根节点到某一节点，路径上的所有字符连接起来为该节点所对应的字符串
• 每个节点的所有子节点的字符各不相同

例题：

最大异或对

n个数中任意两个数进行异或操作，求所有异或对中最大的异或对

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 31 * N;

int a[N], son[M][2], idx = 0, n;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;      //常用位运算操作，查询一个二进制数的第k位（右至左）
        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 res = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        insert(a[i]);           //只需要边查询边插入，每次遍历只需要查询第i个之前的数字
        res = max(res, query(a[i]) ^ a[i]);
    }
    cout << res;
    return 0;
}

思路：

暴力需要进行两重循环，我们优化第二重循环 用Trie树储存数字，每次查询时遵循从高位开始尽量选择与当前第i个数字对应位置不同的数字（异或异1同0），循环31次即可确定出一个与当前第i个数字异或的最大的数字，然后与之前的答案进行max操作