Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。
思路：trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。？ 以及动态开辟内存记得free…？
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月14日 星期日 19时58分41秒
4File Name :code/hdu/1251.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <deque>
20#include <ctime>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26typedef long long LL;
27#define pi pair < int ,int >
28#define MP make_pair
29
30using namespace std;
31const double eps = 1E-8;
32const int dx4[4]={1,0,0,-1};
33const int dy4[4]={0,-1,1,0};
34const int inf = 0x3f3f3f3f;
35char s[20];
36
37struct Trie
38{
39 struct Node
40 {
41 Node *nxt[26];
42 int cnt;
43 Node()
44 {
45 for ( int i = 0 ; i < 26; i++) nxt[i]=NULL;
46 cnt = 0 ;
47 }
48 };
49 Node *root;
50 void init()
51 {
52 root = new Node();
53 }
54 Trie()
55 {
56 root = new Node();
57 }
58 void Insert(char *s)
59 {
60 Node *u = root;
61 int len = strlen(s);
62 for ( int i = 0 ; i < len ; i++)
63 {
64 int v = s[i]-'a';
65 if (u->nxt[v]==NULL) u->nxt[v]=new Node();
66 u = u->nxt[v];
67 u->cnt++;
68 }
69 }
70 int Find(char *s)
71 {
72 Node *u = root;
73 int len = strlen(s);
74 for ( int i = 0 ; i < len ; i++)
75 {
76 int v = s[i]-'a';
77 if (u->nxt[v]==NULL) return 0;
78 u = u->nxt[v];
79 }
80 return u->cnt;
81 }
82
83}trie;
84int main()
85{
86 #ifndef ONLINE_JUDGE
87 freopen("code/in.txt","r",stdin);
88 #endif
89
90 while (gets(s))
91 {
92 int len = strlen(s);
93 if (len==0) break;
94 trie.Insert(s);
95 }
96 while (gets(s))
97 {
98 int ans = trie.Find(s);
99 printf("%d\n",ans);
100 }
101
102 #ifndef ONLINE_JUDGE
103 fclose(stdin);
104 #endif
105 return 0;
106}