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[]; // 指向各个子树的指针
bool exist; // 标记该结点处是否构成单词
}TrieNode , *Trie; Trie createTrieNode()
{
TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
node->count = ;
node->exist = false;
memset(node->next , , 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 += ; // 包括统计每个单词出现的次数
}
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 ;
}
return node->count;
} int main()
{
Trie root = createTrieNode(); // 字典树的根节点
char str[] ;
bool flag = false;
int n ,m ;
scanf ("%d", &n);
for( int i = ; i < n ; i++)
{
scanf ("%s", str);
Trie_insert(root , str);
}
scanf ("%d", &m);
for( int i = ; i < m ; i++)
{
scanf ("%s", str);
printf("%d\n",Trie_search(root , str));
}
return ;
}
#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[];
bool exist; // 标记该结点处是否构成单词
struct Trie_node* prev; //前缀节点
}TrieNode , *Trie; Trie createTrieNode()
{
TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
node->prev=NULL;
node->count = ;
node->exist = false;
memset(node->next , , 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 += ; // 统计每个单词出现的次数
}
node->exist = true; // 单词结束的地方标记
} void Trie_build(Trie root) //Trie树和Tie图的区别就在于此，类似于KMP构造失配函数的一个过程
{
queue<Trie> Q; //利用bfs构造prev指针，队列实现BFS
Trie node=root;
for(int i=;i<;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=; i<; 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[] ;
int main()
{
Trie root = createTrieNode(); // 初始化字典树的根节点
bool flag = false;
int n ;
scanf ("%d", &n);
for( int i = ; 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 ;
}