C++自定义字典树结构

代码

#include <iostream>
using namespace std;class TrieNode
{
public:char data;TrieNode* children[26];bool isTerminal;TrieNode(char ch){data = ch;for (int i = 0; i < 26; i++){children[i] = NULL;}isTerminal = false;}
};
class Trie
{
public:TrieNode* root;Trie(){root = new TrieNode('\0');}void insertUtil(TrieNode* root, string word){// base caseif (word.length() == 0){root->isTerminal = true;return;}// assumption , world will be CAPSint index = word[0] - 'A';TrieNode* child;// presentif (root->children[index] != NULL){child = root->children[index];}else{// absentchild = new TrieNode(word[0]);root->children[index] = child;}// RECURSIONinsertUtil(child, word.substr(1));}void insertWord(string word){insertUtil(root, word);}bool searchUtil(TrieNode* root, string word){// base caseif (word.length() == 0){return root->isTerminal;}int index = word[0] - 'A';TrieNode* child;// presentif (root->children[index] != NULL){child = root->children[index];}else{// absentreturn false;}// RECURSIONreturn searchUtil(child, word.substr(1));}bool searchWord(string word){return searchUtil(root, word);}
};#include <bitset>
#include <unordered_map>
#include <vector>
template <std::size_t N>
using Signature = std::bitset<N>;// util function to split string into parts by given delimiter.
static void split(std::string_view s, std::vector<std::string>& parts, char delimiter) {parts.emplace_back();for (auto ch : s) ch == delimiter ? parts.push_back("") : parts.back().push_back(ch);
};// A MyTrie structures ids by names into a tree.
template <std::size_t N>
class MyTrie {
private:// Signature of all signals under this tree.// e.g. the node `b` matches all "a.b.*"Signature<N> signature;// Child tries.std::unordered_map<std::string, MyTrie*> children;// If it's a end node of a signal's name, the signal id of which.size_t id = 0;char m_delimiter;public:MyTrie(char delimiter = '.') : m_delimiter(delimiter){}~MyTrie() {  // free every child recursivelyfor (auto p : children) delete p.second;}// Puts a signal id onto this tree by signal name.void Put(std::string_view name, size_t id) {std::vector<std::string> parts;split(name, parts, m_delimiter);auto t = this;  // t is the node walked throughfor (const auto& p : parts) {// Creates a node if not exist.if (auto [it, inserted] = t->children.try_emplace(p, nullptr); inserted) it->second = new MyTrie();// Mark this signal id to its signature.t->signature[id] = 1;t = t->children[p];}// The last node.t->id = id;}// Match signals by given pattern, returns a signature of matched signal ids.Signature<N> Match(std::string_view pattern) const {Signature<N> sig;std::vector<std::string> parts;split(pattern, parts, m_delimiter);auto t = this;for (const auto& p : parts) {// matches all under the subtreeif (p == "*")return t->signature;else {  // match by exact name// match failure, returns empty signatureif (t->children.find(p) == t->children.end()) return sig;t = t->children.at(p);}}// The last node, matches a single signal.sig[t->id] = 1;return sig;}
};int test()
{// 基础添加查找，单个字符为一组，进行字符串词典构建Trie* t = new Trie();t->insertWord("ARM");t->insertWord("DO");t->insertWord("TIME");cout << "Present or Not " << t->searchWord("TIM") << endl;  // Present or Not 0cout << "Present or Not " << t->searchWord("TIME") << endl; // Present or Not 1// 扩展模式匹配，单个字符串为一组，进行字符串词典构建MyTrie<1024> trie;trie.Put("ab.cd.ef", 1);trie.Put("ab.cd.kk", 2);trie.Put("ab.xy.zz", 3);trie.Put("tt.xx", 4);trie.Put("ab.cd", 5);auto m1 = trie.Match("ab.cd.ef");   // m1.count() == 1auto m2 = trie.Match("ab.cd.*");   // m2.count() == 2// 字体查找MyTrie<1024> fontlist(' ');std::vector<std::string> familys = {"Noto Sans SC", "Noto Sans ", "Noto Sans Regular", "Noto Sans Bold", "Noto Sans Italic"};int i = 0;for (const auto& family : familys) {fontlist.Put(family, i++);}auto findList = fontlist.Match("Noto Sans *");for (int i = 0; i < familys.size(); i++) {if (findList[i]) {std::cout << familys[i] << std::endl;}}return 0;
}