#include <vector>
#include<cstring>
#include<iostream>
#include <set>
#include <algorithm>
using namespace std;
#define INF 1000000;
//引用只是纯粹的一个变量的别名，至于怎么做到的和指针无关，和语言设计方法有关，待深究；
typedef struct node{
char c;
node *firstchild,*nextsibling;
node():c('\0'),firstchild(NULL),nextsibling(NULL){}
}node,*pointer;
/* 指针版本的左孩子，右兄弟表示法；
插入元素和查找元素的速度为最坏情况下 26*strlen(str);
但对于遍历整棵树而言花费时间代价很低；
*/
struct Trie{
pointer root;
Trie(){root=new node();}
void insert(char* s,int i,int n,pointer& root){
if(i==n) return ;
pointer u=root; //必须用一个新指针，不然下面操作改变了root的指向；
if(u!=NULL) while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling;
if(u==NULL||u->nextsibling==NULL&&u->c!=s[i]){
pointer& v = (u==NULL ? root:u->nextsibling);//NULL时必须赋值为root，因为要改变该指针的指向；
v=new node();
v->c=s[i];
insert(s,i+1,n,v->firstchild);
}
else insert(s,i+1,n,u->firstchild);
}
void Insert(char* s){
int n=strlen(s);
insert(s,0,n,root);
}
bool find(char* s,int i,int n,pointer& root){
if(i==n) return true;
pointer u=root;
if(u==NULL) return false;
while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling;
if(u->nextsibling==NULL&&u->c!=s[i]) return false;
return find(s,i+1,n,u->firstchild);
}
bool Find(char* s,int n){
return find(s,0,n,root);
}
};
int main()
{
char str[1000];
Trie trie;
while(gets(str)!=NULL&&str[0]!='#'){
trie.Insert(str);
}
while(gets(str)!=NULL){
if(trie.Find(str,strlen(str))) printf("find\n");
else printf("not find\n");
}
return 0;
}
上述插入和建树用的是递归的方式；
而循环版本并不好写（每到一个结点都是站在结点的孩子头上，而不是父亲指针那里，所以写起来很麻烦），因为同s[i] -- > s[i+1] 下一次要用的指针必须为某个特定指针，只能通过递归传引用
void insert(char* s,int n){pointer& Root=root;for(int i=0;i<n;i++){ pointer u=Root; if(u!=NULL)while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling; if(u==NULL||u->nextsibling==NULL&&u->c!=s[i]){ pointer& v=(u==NULL ? Root:u->nextsibling);
v=new node(); v->c=s[i]; Root=v->firstchild; } else Root=u->firstchild;（这样的写法错误，因为Root为根结点的引用，对它的修改即修改了根结点）}}
每次都站在父节点上考虑，就好写多，下面为指针--循环版；
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef struct node{
char c;
node *firstchild,*nextsibling;
node():c('\0'),firstchild(NULL),nextsibling(NULL){}
}node,*pointer;
struct Trie{
pointer root;
Trie(){root=new node();}
void insert(char* s,int n){
pointer u=root;
for(int i=0;i<n;i++){
pointer v=u->firstchild;
if(v!=NULL) while(v->nextsibling!=NULL&&v->c!=s[i]) v=v->nextsibling;
if(v==NULL||v->nextsibling==NULL&&v->c!=s[i]){
pointer& p=(v==NULL ? u->firstchild:v->nextsibling);
p=new node();
p->c=s[i];
u=p;
}
else u=v;
}
}
bool find(char* s,int n){
pointer u=root;
for(int i=0;i<n;i++){
pointer v=u->firstchild;
if(v==NULL) return false;
while(v->nextsibling!=NULL&&v->c!=s[i]) v=v->nextsibling;
if(v->nextsibling==NULL&&v->c!=s[i]) return false;
u=v;
}
return true;
}
};
int main()
{
char str[1000];
Trie trie;
while(gets(str)!=NULL&&str[0]!='#'){
trie.insert(str,strlen(str));
}
while(gets(str)!=NULL){
if(trie.find(str,strlen(str))) printf("find\n");
else printf("not find\n");
}
return 0;
}
pointer p=p1; 指针p的指向与p1相同（对p而言，指向改变，而对p1而言多了一个和他指向同一块内存区域的指针）；
pointer& p=p1；对p1而言多了一个可以用的名字；
第三点，就是改变发生的情况不同。
下面为左孩子，右兄弟的数组表示方法
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct Trie{
static const int maxn = 100001;
Trie():tot(2){
memset(firstchild,0,sizeof(firstchild));
memset(nextsibling,0,sizeof(nextsibling));
memset(c,0,sizeof(c));
}
char c[maxn];
int firstchild[maxn],nextsibling[maxn],tot;
void insert(char* s,int n){
int u=1;
for(int i=0;i<n;i++){
int v=firstchild[u];
if(v!=0) while(nextsibling[v]!=0&&c[v]!=s[i]) v=nextsibling[v];
if(!v||nextsibling[v]==0&&c[v]!=s[i]){
int& p=(v==0 ? firstchild[u]:nextsibling[v]);
p=tot;
c[tot]=s[i];
u=tot++;
}
else u=v;
}
}
bool find(char* s,int n){
int u=1;
for(int i=0;i<n;i++){
int v=firstchild[u];
if(!v) return false;
while(nextsibling[v]!=0&&c[v]!=s[i]) v=nextsibling[v];
if(nextsibling[v]==0&&c[v]!=s[i]) return false;
else u=v;
}
return true;
}
};
int main()
{
char str[1000];
Trie trie;
while(gets(str)!=NULL&&str[0]!='#'){
trie.insert(str,strlen(str));
}
while(gets(str)!=NULL){
if(trie.find(str,strlen(str))) printf("find\n");
else printf("not find\n");
}
return 0;
}
下面为用孩子数组实现的版本
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
/*
孩子数组表示法
（即将每个结点的孩子存下来，图是用标号链接的每个结点的内容，用附加数组表示）
本表示方法的试用于总结点数（maxn）较少的情况；
遍历整棵树非常费时，
但在插入和查找的时候是o（strlen（str））的时间；
*/
struct Trie{
static const int maxn = 10000;
static const int sigma_size = 27;
int tot,c[maxn],son[maxn][sigma_size];
Trie():tot(2){memset(son,-1,sizeof(son));}
void insert(char* s,int n){
int u=1;
for(int i=0;i<n;i++){
int word=s[i]-'a';
if(son[u][word]==-1){
son[u][word]=tot;
u=tot++;
}
else u=son[u][word];
}
}
bool find(char* s,int n){
int u=1;
for(int i=0;i<n;i++){
int word=s[i]-'a';
if(son[u][word]==-1) return false;
u=son[u][word];
}
return true;
}
};
int main()
{
char str[1000];
Trie trie;
while(gets(str)!=NULL&&str[0]!='#'){
trie.insert(str,strlen(str));
}
while(gets(str)!=NULL){
if(trie.find(str,strlen(str))) printf("find\n");
else printf("not find\n");
}
return 0;
}