Trie树

原理

  Trie树又叫字典树，可以快速插入和查询某一字符串是否在当前集合之中。限制条件是当前字符集合所有字符总数不能太大，否则效率低下且耗费空间。

  这里存储树是通过son[N][26]类型的二维数组来存储，本质是一个单向查询函数，其中son的第一个维度为当前指针地址，用idx从0开始分配。树根被分配为0，之后依次分配地址递增。第二个维度26是当前确定的字符，当确定了当前节点和当前字符之后，就确定了son中存储值，即下一个节点的地址。通过这种逻辑来用数组存储树和图是一种较为方便和快捷的方法。

  AC自动机是Trie树和KMP算法的结合，通过KMP算法的ne数组在Trie树上进行匹配，完成多个模板串在某一原串中出现次数的统计。

模板

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;

int son[N * 32][2];
int val[N * 32];
int idx;
int n;

void build(int x)
{
    int p = 0;
    for (int i = 31; i >= 0; i -- )
    {
        int t = x >> i & 1;
        if (!son[p][t]) son[p][t] = ++ idx;
        p = son[p][t];
    }

    val[p] = x;
}

int query(int x)
{
    int p = 0;
    for (int i = 31; i >= 0; i -- )
    {
        int t = x >> i & 1;
        if (!son[p][!t]) p = son[p][t];
        else p = son[p][!t];
    }

    return x ^ val[p];
}

int main()
{
    scanf("%d", &n);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t;
        scanf("%d", &t);

        res = max(res, query(t));
        build(t);
    }

    printf("%d\n", res);
    return 0;
}

例题

AW.143 最大亦或对（简单）