首页 > 代码库 > hiho一下 第二周&第四周：从Trie树到Trie图
hiho一下 第二周&第四周：从Trie树到Trie图
hihocoder #1014 题目地址：http://hihocoder.com/problemset/problem/1014
hihocoder #1036 题目地址: http://hihocoder.com/problemset/problem/1036
trie图其实就是trie树+KMP
#1014trie树
#include<stdio.h>#include <algorithm>#include <cstring>#include <string.h>#include <iostream>#include <list>#include <map>#include <set>#include <stack>#include <string>#include <utility>#include <vector>#include <cstdio>#include <cmath>using namespace std; typedef struct Trie_node { int count; // 统计单词前缀出现的次数 struct Trie_node* next[26]; // 指向各个子树的指针 bool exist; // 标记该结点处是否构成单词 }TrieNode , *Trie;Trie createTrieNode(){ TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode)); node->count = 0; node->exist = false; memset(node->next , 0 , sizeof(node->next)); // 初始化为空指针 return node;}void Trie_insert(Trie root, char* word){ Trie node = root; char *p = word; int id; while( *p ) { id = *p - ‘a‘; if(node->next[id] == NULL) { node->next[id] = createTrieNode(); } node = node->next[id]; ++p; node->count += 1; // 包括统计每个单词出现的次数 } node->exist = true; // 可以构成一个单词}int Trie_search(Trie root, char* word){ Trie node = root; char *p = word; int id; while( *p ) { id = *p - ‘a‘; node = node->next[id]; ++p; if(node == NULL) return 0; } return node->count;}int main(){ Trie root = createTrieNode(); // 字典树的根节点 char str[12] ; bool flag = false; int n ,m ; scanf ("%d", &n); for( int i =0 ; i < n ; i++) { scanf ("%s", str); Trie_insert(root , str); } scanf ("%d", &m); for( int i =0 ; i < m ; i++) { scanf ("%s", str); printf("%d\n",Trie_search(root , str)); } return 0;}
#1036trie图
其实就是trie树+KMP
数据结构与trie树一样，加了一个prev指针，作用类似于KMP的失配函数next[]
Trie_insert函数不变
添加一个构造prev的函数Trie_build()。
prev指针的作用：在匹配失败时跳转到具有公共前缀的字符继续匹配，类似于KMP的失配函数next[]。
利用bfs构造prev指针。
指针prev指向与字符p相同的结点，如果没有与p前缀相同的节点，则指向root
根节点的前缀是根节点
最后字符匹配的Trie_search()函数类似于KMP的过程，在当前字符匹配失败时，利用prev指针跳转到具有最长公共前后缀的字符继续匹配。
#include<stdio.h>#include <algorithm>#include <cstring>#include <string.h>#include <iostream>#include <list>#include <map>#include <set>#include <stack>#include <string>#include <utility>#include <queue>#include <vector>#include <cstdio>#include <cmath>using namespace std; typedef struct Trie_node { int count; // 统计单词前缀出现的次数 struct Trie_node* next[26]; bool exist; // 标记该结点处是否构成单词 struct Trie_node* prev; //前缀节点 }TrieNode , *Trie;Trie createTrieNode(){ TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode)); node->prev=NULL; node->count = 0; node->exist = false; memset(node->next , 0 , sizeof(node->next)); return node;}void Trie_insert(Trie root, char* word){ Trie node = root; char *p = word; int id; while( *p ) { id = *p - ‘a‘; if(node->next[id] == NULL) { node->next[id] = createTrieNode(); } node = node->next[id]; ++p; node->count += 1; // 统计每个单词出现的次数 } node->exist = true; // 单词结束的地方标记}void Trie_build(Trie root) //Trie树和Tie图的区别就在于此，类似于KMP构造失配函数的一个过程{ queue<Trie> Q; //利用bfs构造prev指针，队列实现BFS Trie node=root; for(int i=0;i<26;i++)//根节点的子节点的rev都是根节点，根节点的prev也是根节点 { if(node->next[i]!=NULL) { node->next[i]->prev=root; Q.push(node->next[i]); } } while(!Q.empty()) { node=Q.front(); Q.pop(); for(int i=0; i<26; i++) { Trie p=node->next[i]; if(p!=NULL&&p->exist==false) //若此处能构成单词则不用处理prev { Trie prev=node->prev; //上一个结点的前缀节点 while(prev) { if(prev->next[i]!=NULL) { p->prev=prev->next[i]; //prev指向与字符p相同的结点 if(p->prev->exist==true) p->exist=true; break; } else prev=prev->prev; } if(p->prev==NULL)//如果没有与p前缀相同的节点，则指向root p->prev=root; Q.push(p); } } }}bool Trie_search(Trie root, char* word){ Trie node = root; char *p = word; int id; while( *p ) { id = *p - ‘a‘; while(true) { if(node->next[id]!=NULL) //匹配成功 { node = node->next[id]; if(node->exist) return true; break; } else node=node->prev; //类似KMP的失配过程，在当前字符匹配失败时，跳转到具有最长公共前后缀的字符继续匹配 if(node==root||node==NULL){ node=root; break; } } p++; } return false;} char str[1000005] ;int main(){ Trie root = createTrieNode(); // 初始化字典树的根节点 bool flag = false; int n ; scanf ("%d", &n); for( int i =0 ; i < n ; i++) { scanf ("%s", str); Trie_insert(root , str); } Trie_build(root); scanf ("%s", str); if(Trie_search(root , str)) printf("YES\n"); else printf("NO\n"); return 0;}
hiho一下 第二周&第四周：从Trie树到Trie图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。