1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
|
#include<iostream> #include<cstring> #include<map> using namespace std; class Trie{ private: class Node{ public: bool isWord; map<char,Node> *next; Node(bool isWord){ this->isWord=isWord; next=new map<char,Node>(); } Node(){ this->isWord=false; } }; Node *root; int size; public: Trie(){ root=new Node(); size=0; }
//获得Trie中存储的单词数量 int getSize(){ return size; } //向Trie中添加一个新的单词word void add(string word){ Node *cur=root; for(int i=0;i<word.size();i++){ char c=word[i]; if(cur->next->find(c)==cur->next->end()){ cur->next->insert(pair<char,Node>(c,Node())); } cur=&cur->next->find(c)->second; } if(!cur->isWord){ cur->isWord=true; size++; } } //查询单词word是否在Trie中 bool contains(string word){ Node *cur=root; for(int i=0;i<word.size();i++){ char c=word[i]; if(cur->next->find(c)==cur->next->end()){ return false; } cur=&cur->next->find(c)->second; } return cur->isWord; }
//查询是否在Trie中有单词以prefix为前缀 bool isPrefix(string prefix){ Node *cur=root; for(int i=0;i<prefix.size();i++){ char c=prefix.at(i); if(cur->next->find(c)==cur->next->end()) return false; cur=&cur->next->find(c)->second; } return true; }
}; int main(){
return 0; }
|
近期评论