Trie树入门
统计难题 ( hud-1251 )
指针多叉树
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define maxn 26
struct Trie
{
int num;//到某一层字符数目
struct Trie *next[maxn];//每层最多多少种字符
};
struct Trie *root = (struct Trie*)malloc(sizeof(struct Trie));
void init()
{
/*别忘了给root分配内存*/
root->num = 0;
for(int i = 0 ; i < maxn ; ++i)
root->next[i] = NULL;
}
void put(char *str)//插入字典树
{
int len = strlen(str);
struct Trie *p = root;//先由p指向字典树的根，从而找到这棵字典树
//把字符加入字典树
for(int i = 0 ; i < len ; ++i)
{
int pos = str[i] - 'a';//转化为坐标
if(p->next[pos] == NULL)//如果指向的结点为空，新建结点
{
//new一个新结点
struct Trie *temp = (struct Trie*)malloc(sizeof(struct Trie));
temp->num = 1;//这个地方是1说明添加了一个字符
for(int j = 0 ; j < maxn ; ++j)
temp->next[j] = NULL;
p->next[pos] = temp;
p = p->next[pos];
}
else
{
p = p->next[pos];//移动到一下层
p->num++;
}
}
}
int research(char *str)
{
struct Trie *p = root;
int len = strlen(str);
for(int i = 0 ; i < len ; ++i)
{
int pos = str[i] - 'a';
p = p->next[pos];
if(p == NULL)
return 0;
}
return p->num;
}
void del(Trie *p)
{
if(p==NULL) return;
for(int i=0;i<maxn;i++)
{
if(p->next[i]!=NULL)
del(p->next[i]);
}
if(p!=root) free(p);//delete对应的是new；free用来释放malloc出来动态内存
}
int main()
{
char s[15];
init();//初始化字典树，让根节点为空
while(gets(s) && strlen(s))
put(s);//每读取一条记录就加入字典树
while(gets(s))
{
int ans = research(s);
printf("%d\n",ans);
}
return 0;
}
数组多叉树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int MAXN=4000010;
struct Node
{
int sum;
int next[26];
};
Node trie[MAXN];
int trie_s;
void insert(char *str)
{
int len=strlen(str);
int p=0;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(!trie[p].next[pos])
{
trie[p].next[pos]=trie_s++;
}
trie[trie[p].next[pos]].sum++;
p=trie[p].next[pos];
}
}
int query(char *str)
{
int len=strlen(str);
int p=0;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(!trie[p].next[pos]) return 0;
p=trie[p].next[pos];
}
return trie[p].sum;
}
int main()
{
char s[15];
trie_s=1;
char c;
while(true)
{
int index=0;
c=getchar();
if(c=='\n') break;
s[index++]=c;
while(true)
{
c=getchar();
if(c=='\n')
{
s[index++]=0;
break;
}
s[index++]=c;
}
insert(s);
}
while(scanf("%s",s)!=EOF)
{
printf("%d\n",query(s));
}
return 0;
}
左儿子右兄弟树
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 4000010
struct node
{
char y;
int son;
int right;
int sum;
}trie[maxn];
char str[15];
int trie_s ;
long long sum ;
void init()
{
trie[0].son = trie[0].right = -1;
trie[0].sum = 0;
sum = 0;
trie_s = 1;
}
void put()
{
int i , v , k = strlen(str);
int u = 0;
bool flag;
for(i = 0;i<k;i++)
{
flag = false;
for(v = trie[u].son ; v!= -1 ; v = trie[v].right)
{
if(trie[v].y == str[i])
{
trie[v].sum++;
flag = true;
break;
}
}
if(!flag)
{
v = trie_s++;
trie[v].right = trie[u].son;
trie[v].y = str[i];
trie[u].son = v;
trie[v].sum = 1;
trie[v].son = -1;
}
u = v;
}
}
int research()
{
int i , v , k = strlen(str);
int u = 0;
bool flag;
for(i = 0; i <k ; i++)
{
flag = false;
for(v = trie[u].son ; v!= -1 ; v = trie[v].right)
{
if(trie[v].y == str[i])
{
flag = true;
break;
}
}
if(!flag)
{
return 0;
}
u = v;
}
return trie[u].sum;
}
int main()
{
init();
while(gets(str) && strlen(str))
put();
while(gets(str))
{
int ans = research();
printf("%d\n",ans);
}
return 0;
}
