首页 > 编程语言 >算法【前缀树】

算法【前缀树】

时间：2024-08-04 16:56:15浏览次数：17  
标签：前缀 int ++ 算法 trie 节点 cur

注意：学习本篇最少应知道什么是树结构和哈希表怎么用。

前缀树又叫字典树，英文名trie。每个样本 都从头节点开始 根据 前缀字符或者前缀数字 建出来的一棵大树，就是前缀树。没有路就新建节点；已经有路了，就复用节点。

前缀树的使用场景：需要根据前缀信息来查询的场景

前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间

前缀树的缺点：比较浪费空间，和总字符数量有关，字符的种类有关

一、前缀树的原理和代码

前缀树是通过多个节点之间的路来存储信息，并进行快速查询的。比如我们有一个字符串"abc"，从1节点开始（0节点弃用，具体原因后面说明），注意，在前缀树中，节点不存储字符串信息，节点一般有pass和end两个属性，分别表示经过这个节点的次数和以这个节点做结尾的次数。用节点之间的路来存储字符串信息，比如1节点到2节点之间的路代表'a'，2节点到3节点之间的路代表'b'，3节点到4节点之间的路代表'c'。之后再存储字符串就会有节点复用、路复用，比如再来一个字符串"abd"，从1节点开始直到3节点都一样，然后3节点没有代表'd'的路，所以新建节点、新建路，3节点到5节点之间的路代表'd'。在加入两个字符串后，1~5节点pass分别为[2, 2, 2, 1, 1]，end分别为[0, 0, 0, 1, 1]。这样，一个前缀树的结构就建好了，之后对于前缀信息的查询将会非常快速。

对于实现前缀树，一般有两种方式。

类描述的实现方式。不推荐，虽然最常用。

  1. 路的可能性范围较小，用固定数组实现路
  2. 路的可能性范围较大，用哈希表实现路

静态数组的实现方式。推荐，不仅笔试，就连比赛也能保证使用。

  1. 一切都是静态数组来实现，提交准备好够用的空间
  2. 如果路的可能性范围较大，就用每一位的信息建树

下面就介绍静态数组的实现方式。

其中的方法如下所示。

// 将字符串word插入前缀树中
void insert(string word);
// 返回前缀树中字符串word的实例个数
int search(string word);
// 返回前缀树中以prefix为前缀的字符串个数
int prefixNumber(string prefix);
// 从前缀树中移除字符串word
void delete(string word);

测试链接：https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b

我们用一个m×n的二维数组trie存储节点和节点之间路的代表，m表示最大节点个数，一定保证节点不会不够用，n表示路的所有可能性，比如对于小写英文字符串n就是26，而trie[i][j]表示i节点通过代表j的路到trie[i][j]节点上了。然后，每个节点的pass和end属性用两个m长度的一维数组表示，arr[i]表示i节点的pass或end值为arr[i]。

代码如下。

#include <iostream>
#include <string>
using namespace std;
#define MAX_VALUE  200000
int trie[MAX_VALUE][26] = {0};
int Pass[MAX_VALUE] = {0};
int End[MAX_VALUE] = {0};
int m;
int cnt = 1;
void insert(string word) {
    int cur = 1;
    Pass[cur]++;
    for (int i = 0; i < word.size(); ++i) {
        if (trie[cur][word[i] - 'a'] == 0) {
            trie[cur][word[i] - 'a'] = ++cnt;
            cur = trie[cur][word[i] - 'a'];
            Pass[cur]++;
        } else {
            cur = trie[cur][word[i] - 'a'];
            Pass[cur]++;
        }
    }
    End[cur]++;
}
void Delete(string word) {
    int cur = 1;
    Pass[cur]--;
    for (int i = 0; i < word.size(); ++i) {
        cur = trie[cur][word[i] - 'a'];
        Pass[cur]--;
    }
    End[cur]--;
}
bool search(string word) {
    int cur = 1;
    for (int i = 0; i < word.size(); ++i) {
        if (trie[cur][word[i] - 'a'] == 0) {
            return false;
        }
        cur = trie[cur][word[i] - 'a'];
    }
    return End[cur] != 0;
}
int prefixNumber(string pre) {
    int cur = 1;
    for (int i = 0; i < pre.size(); ++i) {
        if (trie[cur][pre[i] - 'a'] == 0) {
            return 0;
        }
        cur = trie[cur][pre[i] - 'a'];
    }
    return Pass[cur];
}
int main() {
    int op;
    string s;
    cin >> m;
    for (int turn = 0; turn < m; ++turn) {
        cin >> op;
        getchar();
        cin >> s;
        switch (op) {
            case 1:
                insert(s);
                break;
            case 2:
                Delete(s);
                break;
            case 3:
                cout << (search(s) ? "YES" : "NO") << endl;
                break;
            case 4:
                cout << prefixNumber(s) << endl;
                break;
        }
    }
}

其中，将trie数组中的0试做未给节点分配路，所以0节点弃而不用，以防产生歧义。

下面将通过几个题目进一步加深理解前缀树和其应用。

二、前缀树的相关题目

题目一

测试链接：https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932

分析：这个就是将a数组前后相减处理后放入前缀树，然后对b数组做同样处理后，查询以b数组为前缀的个数。注意，因为以一个差值作为路代表，路的种类过多，所以将整数差开处理，即比如"32"，处理为"3""2"，然后每个数结束后增加"#"作为数之间的分隔符。这样路的种类只需12种，0~9，'#'，'-'。代码如下。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param b int整型vector<vector<>>
     * @param a int整型vector<vector<>>
     * @return int整型vector
     */
    int trie[2000000][12] = {0};
    int Pass[2000000] = {0};
    int End[2000000] = {0};
    int cnt = 1;
    void insert(string word) {
        int cur = 1;
        Pass[cur]++;
        for (int i = 0; i < word.size(); ++i) {
            int path = (word[i] == '#' ||
                        word[i] == '-') ? (word[i] == '#' ? 11 : 10) : (word[i] - '0');
            if (trie[cur][path] == 0) {
                trie[cur][path] = ++cnt;
                cur = trie[cur][path];
                Pass[cur]++;
            } else {
                cur = trie[cur][path];
                Pass[cur]++;
            }
        }
        End[cur]++;
    }
    int prefixNumber(string pre) {
        int cur = 1;
        for (int i = 0; i < pre.size(); ++i) {
            int path = (pre[i] == '#' ||
                        pre[i] == '-') ? (pre[i] == '#' ? 11 : 10) : (pre[i] - '0');
            if (trie[cur][path] == 0) {
                return 0;
            }
            cur = trie[cur][path];
        }
        return Pass[cur];
    }

    string transfer(int num) {
        string s = "";
        int arr[10];
        int left = 0;
        int right = 0;
        while (num != 0) {
            arr[right++] = num % 10;
            num /= 10;
        }
        while (left < right) {
            s += (arr[--right] + '0');
        }
        s += '#';
        return s;
    }

    vector<int> countConsistentKeys(vector<vector<int>>& b,
                                    vector<vector<int>>& a) {
        vector<int> ans;
        for (int i = 0; i < a.size(); ++i) {
            string s = "";
            for (int j = 1; j < a[i].size(); ++j) {
                int num = a[i][j] - a[i][j - 1];
                s += transfer(num);
            }
            insert(s);
        }
        for (int i = 0; i < b.size(); ++i) {
            string s = "";
            for (int j = 1; j < b[i].size(); ++j) {
                int num = b[i][j] - b[i][j - 1];
                s += transfer(num);
            }
            ans.push_back(prefixNumber(s));
        }
        return ans;
    }
};

其中，前缀树的方法只需两个，故将不需要的删除。

题目二

测试链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

分析：由于int型的32位在最左侧的1的左边可能存在多位的0，会增加处理时间，所以只需参考数组中最大值所需要的位数，从而在对数组中每个数进行前缀数插入时，只需要处理相应位数即可。对于数组中的每一位数去寻找到对于这个数能够得到的理想最大异或值。对于这个数，每一位进行判断，如果是1则理想的数，这一位是0；如果是0，理想数的这一位就是1，通过前缀树查询理想数的1或0是否能够得到，如果不能，理想数的这一位就是理想位数的异或值，1变为0，0变为1。得到理想数的这一位数后，对理想数的这一位数和正在处理的数的这一位数的异或结果进行左移相应位数，然后和当前异或结果或求值。处理完所有位数后，即可得到对于这一个数所能得到的最大异或值。然后得到数组中每一位数所能得到的最大异或值，即可求得总体最大异或值。代码如下。

class Solution {
public:
    int trie[3000000][2] = {0};
    int Pass[3000000] = {0};
    int End[3000000] = {0};
    int cnt = 1;
    void insert(int num, int high) {
        int cur = 1;
        Pass[cur]++;
        for (int i = high; i >= 0; --i) {
            int path = (((num >> i) & 1) == 0) ? 0 : 1;
            if (trie[cur][path] == 0) {
                trie[cur][path] = ++cnt;
                cur = trie[cur][path];
                Pass[cur]++;
            } else {
                cur = trie[cur][path];
                Pass[cur]++;
            }
        }
        End[cur]++;
    }
    int prefixNumber(int num, int high, int low) {
        int cur = 1;
        for (int i = high; i >= low; --i) {
            int path = (((num >> i) & 1) == 0) ? 0 : 1;
            if (trie[cur][path] == 0) {
                return 0;
            }
            cur = trie[cur][path];
        }
        return Pass[cur];
    }
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        int m = *(max_element(nums.begin(), nums.end()));
        int bit = 31;
        while ((bit >= 0) && (!((m >> bit) & 1))) {
            --bit;
        }
        for (int i = 0; i < nums.size(); ++i) {
            insert(nums[i], bit);
        }
        for (int i = 0; i < nums.size(); ++i) {
            int desire = 0;
            int cur = 1;
            for (int j = bit, status, want; j >= 0; --j) {
                status = (((nums[i] >> j) & 1) == 0 ? 0 : 1);
                want = status ^ 1;
                if (!trie[cur][want]) {
                    want ^= 1;
                }
                desire |= ((want ^ status) << j);
                cur = trie[cur][want];
            }
            ans = ((ans > desire) ? ans : desire);
        }
        return ans;
    }
};

其中，m是数组中的最大值，bit是需要处理的位数，desire是对于正在处理的数的当前最大异或值，status是正在处理的数某一位的值，want是对于正在处理的数的理想数某一位的值。

当然，这个题如果使用哈希表会更快，不过本文主要是侧重前缀树的解法。下面给出哈希表解法（java）。

import java.util.HashSet;

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        int ans = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 31 - Integer.numberOfLeadingZeros(max); i >= 0; i--) {
            // ans : 31....i+1 已经达成的目标
            int better = ans | (1 << i);
            set.clear();
            for (int num : nums) {
                // num : 31.....i 这些状态保留，剩下全成0
                num = (num >> i) << i;
                set.add(num);
                // num ^ 某状态 是否能 达成better目标，就在set中找 某状态 : better ^ num
                if (set.contains(better ^ num)) {
                    ans = better;
                    break;
                }
            }
        }
        return ans;
    }

}

题目三

测试链接：https://leetcode.cn/problems/word-search-ii/

分析：可以看出，这道题的主体思路是一个回溯算法，那么回溯算法就是在考剪枝能力。我们可以通过前缀树进行三个地方的优化，从而使速度更快。在将所有单词插入前缀树之后，对于board二维数组进行遍历的时候，前缀树可以指导每次进递归对哪个方向进行遍历，这是第一个地方的剪枝。在将一个单词查询到之后，从前缀树上删除这个这个单词的痕迹，从而使后续不再对这个单词进行遍历，这是第二个地方的剪枝。可以在前缀数上把end信息改为字符串信息存储，一个单词结尾节点的end是这个单词的字符串，这个单词的中间节点的end设为空值或者空字符串。这样在遍历到这个单词的结尾节点的时候可以直接获取到这个单词，这是第三个地方的优化。这样由前缀树指导的剪枝回溯，可以使速度大大提升。代码如下。

class Solution
{
public:
    int trie[100000][26] = {0};
    int Pass[100000] = {0};
    string End[100000] = {""};
    int cnt = 1;
    int f(int row, int column, vector<string> &ans, int cur, vector<vector<char>> &board){
        if(row < 0 || row == board.size() || column < 0 || column == board[0].size() || (board[row][column] == 0)){
            return 0;
        }
        char temp = board[row][column];
        int road = temp - 'a';
        cur = trie[cur][road];
        if(Pass[cur] == 0){
            return 0;
        }
        int fix = 0;
        if(End[cur] != ""){
            fix++;
            ans.push_back(End[cur]);
            End[cur] = "";
        }
        board[row][column] = 0;
        fix += f(row-1, column, ans, cur, board);
        fix += f(row+1, column, ans, cur, board);
        fix += f(row, column-1, ans, cur, board);
        fix += f(row, column+1, ans, cur, board);
        Pass[cur] -= fix;
        board[row][column] = temp;
        return fix;
    }
    void build(vector<string> &words){
        cnt = 1;
        for(int i = 0;i < words.size();++i){
            int cur = 1;
            Pass[cur]++;
            for(int j = 0, path;j < words[i].size();++j){
                path = words[i][j] -  'a';
                if(trie[cur][path] == 0){
                    trie[cur][path] = ++cnt;
                }
                cur = trie[cur][path];
                Pass[cur]++;
            }
            End[cur] = words[i];
        }
    }
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        build(words);
        vector<string> ans;
        for(int i = 0;i < board.size();++i){
            for(int j = 0;j < board[0].size();++j){
                f(i, j, ans, 1, board);
            }
        }
        return ans;
    }
};

其中build方法整合和插入方法，f方法是主体回溯函数，同时对于同一条路径，采用遍历过对其ASCII码值赋0实现判断是否被访问。fix是当前节点及后续节点查询到多少单词，然后在前缀树上消除这些单词的痕迹。

标签：前缀,int,++,算法,trie,节点,cur
From： https://blog.csdn.net/W_O_Z/article/details/140881101

相关文章

  • 2024“钉耙编程”中国大学生算法设计超级联赛（4）
    题面：https://files.cnblogs.com/files/clrs97/%E7%AC%AC%E5%9B%9B%E5%9C%BA%E9%A2%98%E9%9D%A2.pdf题解：https://files.cnblogs.com/files/clrs97/%E7%AC%AC%E5%9B%9B%E5%9C%BA%E9%A2%98%E8%A7%A3.pdf Code：A.超维攻坚#include<cstdio>constintN=15,inf=~0U>>......
  • 算法题之旋转链表
    旋转链表给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。示例1：输入：head=[1,2,3,4,5],k=2输出：[4,5,1,2,3]示例2：输入：head=[0,1,2],k=4输出：[2,0,1]提示：链表中节点的数目在范围 [0,500] 内-100<=Node.val<=1000<=k<=......
  • 【机器学习算法基础】（基础机器学习课程）-11-k-means-笔记
        示例案例为了更好地理解K-Means算法，下面通过一个简单的案例进行说明。假设我们有以下10个二维数据点，表示不同商店的销售额（单位：千元）和顾客数（单位：人）：[(10,100),(20,80),(30,70),(40,60),(50,50),(60,40),(70,30),(80,20),(90,10),(......
  • KMP 算法学习笔记
    问题引入给出两个字符串\(s1\)和\(s2\)，求出\(s2\)在\(s1\)中所有出现的位置（出现指\(s1\)中存在子串与\(s2\)完全相同）。朴素暴力不详细介绍，容易发现时间复杂度不优秀。KMP算法思想在朴素暴力中我们可以发现有很多匹配是不需要再次从头开始重新匹配的，举个例子：ABA......
  • 寻求 Kadane 求连续子数组最大和的算法的优化和验证
    在此处输入图像描述给定一个由N个整数组成的数组A。您希望将数组划分为不相交的连续子数组以使其良好。如果满足以下条件，则认为数组是好的数组：每个元素恰好属于一个子数组。如果我们将每个子数组替换为子数组值的MEX（排除最小值），则生成的数组将按非降序......
  • DAY4 前缀和与差分
    本文中将要介绍前缀和与差分的简单知识，全部题目来自acwing，是对y总讲解的简单归纳。题目：acwing795输入一个长度为 n的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l个数到第 r个数的和。输入格式第一行包含两个整数 n和 ......
  • Java计算机毕业设计基于协同过滤算法的音乐推荐系统（开题报告+源码+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着互联网技术的飞速发展，音乐作为人们日常生活中不可或缺的一部分，其获取方式也经历了从实体唱片到数字音乐的巨大变革。面对海量的音乐资源和日益个......
  • Java计算机毕业设计基于协同过滤算法的体育用品推荐系统（开题报告+源码+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着互联网的迅猛发展，电子商务已成为人们购物的主要渠道之一，体育用品市场也不例外。然而，面对海量的体育用品信息和多样化的用户需求，如何高效、精准地......
  • 秒懂斐波那契：算法优化实现21亿级速度突破
    针对斐波那契数列算法进行详细介绍和优化，从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法，最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处，最后可以看到如何实现在输入n=2100000000（21亿）时仅耗时0.02毫秒的最佳效果。一、回顾斐波......
  • DLMS/COSEM中的信息安全：加密算法（中）1
    3.3高级加密标准    为了DLMS/COSEM的目的，应使用FIPSPUB197:2001中规定的高级加密标准（AES）。AES在加密或解密操作期间对数据块（块）进行操作。因此，AES被称为分组密码算法。    AES使用128、192或256位密钥以128位数据块加密和解密数据。三个密钥大小是足够的。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99