二、例题，代码
1.AcWing 835. Trie字符串统计
本博客给出本题截图：
关于本题：
我们在操作过程中，需要一个son[N][26]数组，son[p][u]的作用就是代表着以p为根，u为子节点，我们在插入的过程中，如果以p为根的u的子节点不存在的话，那么就把它创建出来,然后让p = son[p][u]，如果存在p为根的u的子节点的话，直接让p = son[p][u];
if (!son[p][u]) son[p][u] = ++ dix; //为什么不是idx ++; //idx一开始指向，就是我们模拟中的root，故我们在插入元素的时候需要从开始插入，所以为 ++ idx; p = son[p][u];
最后我们的p指向的就是我们的结尾，我们这里去拿一个cnt数组去记录，代表以p为结尾的子串存在，代码为
cnt[p] ++;
AC代码
#include <cstdio> using namespace std; const int N = 100010; char str[N]; int son[N][26], idx, cnt[N]; //为什么是son[N][26]，因为我们只有小写字母 int 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]; } int main() { char op[2]; int n; scanf("%d", &n); while (n -- ) { scanf("%s", op); if (op[0] == 'I') { scanf("%s", str); insert(str); } else { scanf("%s", str); printf("%d\n", query(str)); } } return 0; }
2.AcWing 143. 最大异或对
本题链接：AcWing 143. 最大异或对
本博客给出本题截图：
关于本题
因为我们的节点只有值为1和0这两种情况，所以我们开的son数组的二维是2,
如何取异或后的最大值，从最高位开始，我们要每次尽量取不一样的，这里拿例题中的输入样例去举例：
1的二进制为01
2的二进制为10
3的二进制为11
我们从1开始，1的二进制最高位是0，所以我们要找到第一位是1的，发现2和3的二进制最高位的值恰好是1，所以继续看1的二进制第二位是1，为了让异或的值最大，我们需要找到父节点为1，子节点为0的值，2满足这个条件，所以和1异或后数最大的数是2，1^2 = 3，依次类推，如果我们在找子节点的时候发现没有满足条件的点，那么被迫无奈也只能顺着现有的子节点继续走下去.
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010, M = 31 * N; //一个数的最大位数是31，因为有N个数，所以开辟 M = 31 * N; int a[N], son[M][2]; int n, idx; void insert(int a) { int p = 0; for (int i = 30; ~i; i -- ) { int x = a >> i & 1; if (!son[p][x]) son[p][x] = ++ idx; p = son[p][x]; } } int query(int a) { int p = 0, res = 0; for (int i = 30; ~i; i -- ) { int x = a >> i & 1; if (son[p][!x]) { res = res * 2 + !x; p = son[p][!x]; } else { res = res * 2 + x; p = son[p][x]; } } return res; } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) { scanf("%d", &a[i]); insert(a[i]); } int res = 0; for (int i = 0; i < n; i ++ ) res = max (res, query(a[i]) ^ a[i]); printf("%d", res); return 0; }
三、时间复杂度
关于Trie算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
