ACM:统计难题 解题报告-字典树（Trie树）

#include"iostream"
#include"algorithm"
#include"cstdio"
#include"cstring"
#define MX 110000
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;

struct Trie {
	int v;//v每个字母的次数;
	Trie *next[26];
} root;

void BuildTrie(char *s) {
	int len=strlen(s);
	Trie *p=&root,*q;
	for(int i=0; i<len; i++) {
		int num=s[i]-‘a‘;
		if(p->next[num]==NULL) {
			q=(Trie *)malloc(sizeof(root));//申请一块新内存; //动态分配内存
			q->v=1;
			for(int j=0; j<26; j++) {
				q->next[j]=NULL;		//清空申请内存的所有子节点
			}
			p->next[num]=q;		//往子节点下去继续记录字典树
			p=p->next[num];
		} else {
			p=p->next[num];
			p->v++;					//如果到达此处的字典树已经存在，数加一
		}
	}
}

int Query(char *s) {
	int len=strlen(s);
	Trie *p=&root;
	for(int i=0; i<len; i++) {
		int num=s[i]-‘a‘;
		if(p->next[num]==NULL) {
			return 0;
		}//如果后面一个节点是空的，则说明这个字符串不存在字典树中
		else p=p->next[num];	//否则继续往下查询
	}
	int v=p->v;
	return v;		//如果查询结束，返回这个字符串出现过的次数
}

int main() {
	char s[15];
	for(int i=0; i<26; i++)
		root.next[i]=NULL;
	while(gets(s)&&s[0]!=‘\0‘) {
		BuildTrie(s);
	}
	while(~scanf("%s",s)) {
		printf("%d\n",Query(s));
	}
	return 0;
}