hdu 1251 统计难题 (trie树模板题)
题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。
思路：trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。？ 以及动态开辟内存记得free...？
/* ***********************************************
Author :111qqz
Created Time :2016年08月14日 星期日 19时58分41秒
File Name :code/hdu/1251.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <stack>
8#include <set>
9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <deque>
14#include <ctime>
15#define fst first
16#define sec second
17#define lson l,m,rt<<1
18#define rson m+1,r,rt<<1|1
19#define ms(a,x) memset(a,x,sizeof(a))
20typedef long long LL;
21#define pi pair < int ,int >
22#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6char s[20];
1struct Trie
2{
3 struct Node
4 {
5 Node *nxt[26];
6 int cnt;
7 Node()
8 {
9 for ( int i = 0 ; i < 26; i++) nxt[i]=NULL;
10 cnt = 0 ;
11 }
12 };
13 Node *root;
14 void init()
15 {
16 root = new Node();
17 }
18 Trie()
19 {
20 root = new Node();
21 }
22 void Insert(char *s)
23 {
24 Node *u = root;
25 int len = strlen(s);
26 for ( int i = 0 ; i < len ; i++)
27 {
28 int v = s[i]-'a';
29 if (u->nxt[v]==NULL) u->nxt[v]=new Node();
30 u = u->nxt[v];
31 u->cnt++;
32 }
33 }
34 int Find(char *s)
35 {
36 Node *u = root;
37 int len = strlen(s);
38 for ( int i = 0 ; i < len ; i++)
39 {
40 int v = s[i]-'a';
41 if (u->nxt[v]==NULL) return 0;
42 u = u->nxt[v];
43 }
44 return u->cnt;
45 }
1}trie;
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6 #endif
1 while (gets(s))
2 {
3 int len = strlen(s);
4 if (len==0) break;
5 trie.Insert(s);
6 }
7 while (gets(s))
8 {
9 int ans = trie.Find(s);
10 printf("%d\n",ans);
11 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}