【数据结构】前缀树（字典树)汇总

基础{“a”,“abc”,“bac”,“bbc”,“ca” }的字典树如下图最主用的应用一字符串编码。二位运算。字符串编码相比利用哈希映射编码优点如下依次查询长度为n的字符串s的前缀时间复杂度是O(n)。查询完s[0…i]再查询s[0…i1]的时间复杂度是O(1)。而哈希映射的时间复杂度是O(nn)。利用哈希映射编码的代码如下注意m_iLeafIndex 为-1表示此节点不是任何字符串的结束字符。classCStrToIndex{public:CStrToIndex(){}CStrToIndex(constvectorstringwordList){for(constautostr:wordList){Add(str);}}intAdd(conststringstr){if(m_mIndexs.count(str)){returnm_mIndexs[str];}m_mIndexs[str]m_strs.size();m_strs.push_back(str);returnm_strs.size()-1;}vectorstringm_strs;intGetIndex(conststringstr){if(m_mIndexs.count(str)){returnm_mIndexs[str];}return-1;}protected:unordered_mapstring,intm_mIndexs;};利用字典树编码的代码如下templateclassTDatachar,intiTypeNum26,TData cBeginaclassCTrieNode{public:~CTrieNode(){for(auto[tmp,ptr]:m_dataToChilds){deleteptr;}}CTrieNode*AddChar(TData ele,intiMaxID){#ifdef_DEBUGif((elecBegin)||(elecBeginiTypeNum)){returnnullptr;}#endifconstintindexele-cBegin;autoptrm_dataToChilds[ele-cBegin];if(!ptr){m_dataToChilds[index]newCTrieNode();#ifdef_DEBUGm_dataToChilds[index]-m_iIDiMaxID;m_childForDebug[ele]m_dataToChilds[index];#endif}returnm_dataToChilds[index];}CTrieNode*GetChild(TData ele){#ifdef_DEBUGif((elecBegin)||(elecBeginiTypeNum)){returnnullptr;}#endifreturnm_dataToChilds[ele-cBegin];}protected:#ifdef_DEBUGintm_iID-1;std::unordered_mapTData,CTrieNode*m_childForDebug;#endifpublic:intm_iLeafIndex-1;protected://CTrieNode* m_dataToChilds[iTypeNum] { nullptr };//空间换时间 大约216字节//unordered_mapint, CTrieNode* m_dataToChilds;//时间换空间 大约56字节mapint,CTrieNode*m_dataToChilds;//时间换空间,空间略优于哈希映射数量小于256时时间也优。大约48字节};templateclassTDatachar,intiTypeNum26,TData cBeginaclassCTrie{public:intGetLeadCount(){returnm_iLeafCount;}CTrieNodeTData,iTypeNum,cBegin*AddA(CTrieNodeTData,iTypeNum,cBegin*par,TData curValue){autocurNodepar-AddChar(curValue,m_iMaxID);FreshLeafIndex(curNode);returncurNode;}templateclassITintAdd(IT begin,IT end){autopNodem_root;for(;begin!end;begin){pNodepNode-AddChar(*begin,m_iMaxID);}FreshLeafIndex(pNode);returnpNode-m_iLeafIndex;}templateclassITCTrieNodeTData,iTypeNum,cBegin*Search(IT begin,IT end){autoptrm_root;for(;begin!end;begin){ptrptr-GetChild(*begin);if(nullptrptr){returnnullptr;}}returnptr;}CTrieNodeTData,iTypeNum,cBeginm_root;protected:voidFreshLeafIndex(CTrieNodeTData,iTypeNum,cBegin*pNode){if(-1pNode-m_iLeafIndex){pNode-m_iLeafIndexm_iLeafCount;}}intm_iMaxID0;intm_iLeafCount0;};二进制位运算01前缀树)比如求nums和x的xor最大值。将nums放到01放到前缀树中。通过拆位法依次从高到低处理各位如果x 此为1则优先选择前缀树的0分支如果x为0则优先选择前缀树的1分支。classC2BNumTrieNode{public:C2BNumTrieNode(){m_childs[0]m_childs[1]nullptr;}boolGetNot0Child(boolbFirstRight){autoptrm_childs[bFirstRight];if(ptr(ptr-m_iNum0)){returnbFirstRight;}return!bFirstRight;}intm_iNum0;C2BNumTrieNode*m_childs[2];};templateclassTint,intiLeveCount31classC2BNumTrie{public:C2BNumTrie(){m_pRootnewC2BNumTrieNode();}voidAdd(T iNum){m_setHas.emplace(iNum);C2BNumTrieNode*pm_pRoot;for(intiiLeveCount-1;i0;i--){p-m_iNum;boolbRightiNum((T)1i);if(nullptrp-m_childs[bRight]){p-m_childs[bRight]newC2BNumTrieNode();}pp-m_childs[bRight];}p-m_iNum;}voidDel(T iNum){autoitm_setHas.find(iNum);if(m_setHas.end()it){return;}m_setHas.erase(it);C2BNumTrieNode*pm_pRoot;for(intiiLeveCount-1;i0;i--){p-m_iNum--;boolbRightiNum((T)1i);pp-m_childs[bRight];}p-m_iNum--;}voidSwap(C2BNumTrieT,iLeveCounto){swap(m_pRoot,o.m_pRoot);swap(m_setHas,o.m_setHas);}C2BNumTrieNode*m_pRoot;std::unordered_multisetTm_setHas;};templateclassTint,intiLeveCount31classCMaxXor2BTrie:publicC2BNumTrieT,iLeveCount{public:TMaxXor(T iNum){C2BNumTrieNode*pC2BNumTrieT,iLeveCount::m_pRoot;T iRet0;for(intiiLeveCount-1;i0;i--){boolbRight!(iNum((T)1i));boolbSelp-GetNot0Child(bRight);pp-m_childs[bSel];if(bSelbRight){iRet|((T)1i);}}returniRet;}};题解给字符串编码难道分字典树】 【哈希表】 【字符串】3076. 数组中的最短非公共子字符串1635【字典树前缀树) 字符串】2416. 字符串的前缀分数和需要记录子孙数量1725【字典树 最长公共前缀】1316. 不同的循环子字符串1836【字典树前缀树】1032. 字符流1970【map】【滑动窗口】【字典树】C算法2781最长合法子字符串的长度2203【字典树】【字符串】【 前缀】3093. 最长公共后缀查询2118【字典树】【KMP】【C算法】3045统计前后缀下标对 II2327【字典树 离线查询 深度优先】1938. 查询最大基因差2502动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本2695【动态规划】 【字典树】C算法472 连接词【回溯 字典树前缀树】212. 单词搜索 II【字典树 马拉车算法】336. 回文对【字典树前缀树)】745. 前缀和后缀搜索01前缀树【字典树】2935找出强数对的最大异或值 II2348【字典树前缀树 异或 离线查询】1707. 与数组中元素的最大异或值2358【字典树前缀树 位运算】1803. 统计异或值在范围内的数对有多少2479其它前缀树【字典树前缀树) 哈希映射 后序序列化】1948. 删除系统中的重复文件夹需要DFS2533扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。