【HDU-1251】解题报告（字典树）

原始题目

统计难题

  • Time Limit: 4000/2000 MS (Java/Others)
  • Memory Limit: 131070/65535 K (Java/Others)
  • Total Submission(s): 55180
  • Accepted Submission(s): 19275

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

2
3
1
0

Author

Ignatius.L

Recommend

Ignatius.L

题目大意

如题 # 解题思路 - 字典树裸题，建立字典树时每个单词每个结点权值++ - 访问的时候不在树上输出0，在的话输出结尾结点的权值。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <string>
#include <cstring>
#include <stack>
using namespace std;
const int maxn=1e5+5;
const int maxl=26;

typedef long long ll;
typedef struct Trie
{
	int v;
	Trie* next[maxl];
}Trie;
 
Trie *root;
void iniTrie()
{
	root=(Trie*)malloc(sizeof(Trie));
	for(int i=0;i<maxl;i++)
		root->next[i]=NULL;
	root->v=-1;
}

void creTrie(char* a)
{
	int l=strlen(a);
	Trie *p=root,*q;
	for(int i=0;i<l;i++)
	{
		int id=a[i]-'a';
		//并非前缀不能有相同，而是不能在相同的分支上。 
		if(p->next[id]!=NULL) {
			p=p->next[id];
			p->v++;
		}
		else{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=1;
			for(int j=0;j<maxl;j++) q->next[j]=NULL;
			p->next[id]=q;
			p=p->next[id];
		}

	}

}
//void printTrie()
//{
//	Trie* p=root;
//	stack<Trie*>s;
//	s.push(p);
//	while(!s.empty())
//	{
//		Trie *now=s.top();
//		s.pop();
//		if(now->v==1) printf("%d\n",now->v);
//		for(int i=0;i<maxl;i++)
//			if(now->next[i]!=NULL)
//				s.push(now->next[i]); 
//	}
//}
int printTrie(char* b){
	Trie *p=root;
	int l=strlen(b);
	for(int i=0;i<l;i++){
		int index=b[i]-'a';
		if(p->next[index]!=NULL)
			p=p->next[index];
		else{

			return 0;
		}
	}
	return p->v;
}

void delTrie(Trie *p)  
{  
    int i;  
    for(i=0;i<maxl;i++)  
    {  
        if(p->next[i] != NULL)  
            delTrie(p->next[i]);  
    }  
    free(p);
//    printf("1");
	p==NULL;  
	return ;
}  


int t,ccount;
int main()
{
	char a[20],c;
	iniTrie();
	while(gets(a)&&a[0]!='\0')
		creTrie(a);
	while(~scanf("%s",a))
		printf("%d\n",printTrie(a));
	delTrie(root);
}

收获与反思

  • 字典树裸题，注意建立的时候怎么打标记（染色）。