Trie树专题

本文主要是介绍Trie树专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Intro：

        为了高效的存储和查找字符串，集合的数据结构。，

 板子：

/*Trie树 —— 模板题 AcWing 835. Trie字符串统计*/
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
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] ++ ;
}// 查询字符串出现的次数
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];
}
// 正常遍历完后的p就是指向最后一个字符。

AcWing 835. Trie字符串统计 

#include<iostream>
using namespace std;
int t;
const int N = 1e5 + 10;
int son[N][27], cnt[N], idx;
string x;void insert(string str){int p = 0;for(int i = 0; i < str.length(); i ++){int u =  str[i] - 'a';if(!son[p][u])  son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++;
}int query(string 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(){cin >> t;while (t --){string op;  cin >> op >> x;if(op[0] == 'I')    insert(x);else    cout << query(x) << endl;}return 0;
}

======异或字典树/01字典树======

AcWing 143. 最大异或对

        着重关注一下如何估计结点数目的上限M. 

#include<iostream>
using namespace std;
const int N = 1e5 + 10, M = 30 * N + 10;    
// M是估计节点数目的上限 = 单词个数(N) * 平均单词长度(30)
int a[N], son[M][2], idx;void insert(int x){int p = 0;for(int i = 0; i < 31; i ++){// 错误写法：int u = x & (1 << (30 - i));   与的结果并非-或1int u = (x >> (30 - i)) & 1;if(!son[p][u])  son[p][u] = ++ idx;p = son[p][u];  // 移动}
}// func: 能够与num异或运算得到最大数值的数(在数组中)
int query(int num){int p = 0;int res = 0;for(int i = 0; i < 31; i ++){int u = (num >> (30 - i)) & 1;if(!son[p][!u]) res = (res << 1) + u, p = son[p][u];        // 相反方向不存在else    res = (res << 1) + !u, p = son[p][!u];              // 相反方向存在}return res;
}int main(){int n;  cin >> n;for(int i = 0; i < n; i ++) {cin >> a[i];insert(a[i]);}int res = 0;for(int i = 0; i < n; i ++)res = max(res, a[i] ^ query(a[i]));cout << res;return 0;
}

AcWing 3485. 最大异或和

Leetcode 208. 实现 Trie (前缀树)

注意下search和startswith的判别即可。 

class Trie {
public:const static int N = 3e4 * 20;int son[N][26], cnt[N], idx;
public:Trie() {idx = 0;memset(son, 0, sizeof(son));memset(cnt, 0, sizeof(cnt));}void insert(string word) {int p = 0;for(int i = 0; i < word.length(); i ++){int u = word[i] - 'a';if(!son[p][u])  son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++;}bool search(string word) {int p = 0;for(int i = 0; i < word.length(); i ++){int u = word[i] - 'a';if(!son[p][u])  return false;p = son[p][u];}return cnt[p];}bool startsWith(string prefix) {int p = 0;for(int i = 0; i < prefix.length(); i ++){int u = prefix[i] - 'a';if(!son[p][u])  return false;p = son[p][u];}return true;}
};

Leetcode 676. 实现一个魔法字典 

方法一：(暴力)哈希字符串长度

class MagicDictionary {
public:
unordered_map<int, vector<string>> hash;MagicDictionary() {}void buildDict(vector<string> dictionary) {for(auto& v: dictionary){int len = v.length();hash[len].push_back(v);}}bool search(string searchWord) {int slen = searchWord.length();if(hash.count(slen) == 0)   return false;// 如果长度相等的话,才有可能替换一个字母匹配上int cnt = 0;        // 变成2直接false,for结束若仍然为0也是falsebool fd = false;for(auto& dicstring: hash[slen]){cnt = 0;for(int i = 0; i < slen; i ++){if(dicstring[i] != searchWord[i]){cnt ++;if(cnt == 2)    break;}}   if(cnt == 1){fd = true;  break;}}return fd;}
};

方法二：(Trie)优化枚举+dfs

class MagicDictionary {
public:const static int N = 1e5 + 10;int son[N][26], cnt[N], idx;
public:MagicDictionary() {idx ++;memset(son, 0, sizeof(son));memset(cnt, 0, sizeof(cnt));}void buildDict(vector<string> dictionary) {auto insert = [&](string x) -> void{int p = 0;for(int i = 0; i < x.length(); i ++){int u = x[i] - 'a';if(!son[p][u])  son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++;};for(auto& v: dictionary)    insert(v);}bool search(string searchWord) {function<bool(int, int, int)> dfs=[&](int p, int idx, bool modi)->bool{if(idx == searchWord.size())return modi && cnt[p];   // 修改过一次&&终止int u = searchWord[idx] - 'a';if(son[p][u])  // 存在的话, 可以继续往下走if(dfs(son[p][u], idx + 1, modi))return true;// 如果还没修改过, 可以修改为任意除了原本元素的其他字母if (!modi){for(int i = 0; i < 26; i ++){if (i != u && son[p][i])if(dfs(son[p][i], idx + 1, true))return true;}}return false;};return dfs(0, 0, false);}
};

这篇关于Trie树专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---