题目描述

《字典树基本模板》

【字典树基本模板】 【输入样例】 5 i int integer intern internet 3 in int tern 【输出样例】 0 1 0 #include #include <unordered_map> using namespace std; // 定义了字典树的节点，每个节点包含一个子节点列表和一个标志 isEnd。 struct trieNode{ unordered_map<char, trieNode*> child; // 子结点哈希表<字符，节点指针> bool isEnd; // isEnd表示从根到当前节点的路径是否构成一个完整的字符串。 // 构造函数 trieNode(){ isEnd = false;} }; // 在字典树中插入单词。 root：字典树根节点指针 。 void insert(trieNode* root, string word){ trieNode* curNode = root; //for(int i=0;i < word.length(); i++){ for(char c:word){ // 遍历word的每个字符c , 寻找键c对应的子节点 if(curNode->child.find(c) == curNode->child.end()){ // 若不存在则创建新节点，映射为<c, 新节点> curNode->child[c] = new trieNode(); } curNode = curNode->child[c]; //移到当前字符的子结点 } // 给最后一个字符的节点设置结尾标记 curNode->isEnd = true; } // 找到字符串str最后一个字符对应节点的指针，如果不存在，返回null。 trieNode* find(trieNode* root, string str){ trieNode* curNode = root; for(char c:str){ // 遍历str的每个字符c, 寻找键c对应的子节点 if(curNode->child.find(c) == curNode->child.end()){ // 若不存在，返回空指针 return nullptr; }else{ // 若存在则移动到这个子节点，继续遍历 curNode = curNode->child[c]; } } return curNode; } // 检索完整单词 word 在字典树中是否存在 bool search(trieNode* root, string word){ trieNode* node = find(root, word); return node != nullptr && node->isEnd; } // 检索前缀 prefix 在字典树中是否存在 bool startWith(trieNode* root, string prefix){ trieNode* node = find(root, prefix); return node != nullptr; } int main(){ int n,m; string word; // 初始字典树的根节点 trieNode* root = new trieNode(); // 把 n 个单词插入字典树 cin >> n; for(int i = 1;i <= n;i++){ cin >> word; insert(root, word); } // 进行 m 次检索 cin >> m; for(int i = 1;i <= m;i++){ cin >> word; cout << search(root, word) << endl; } return 0; }

输入格式

无

输出格式

（见样例）

样例

输入样例 1

5
i
int
integer
intern
internet 
3
in
int
tern

输出样例 1

0
1
0