2390:查单词PowerOJ（字典树）

Description
XX 最近遇到一个难题&＃xff1a;老师交给他一本字典&＃xff0c;这本字典里有100000 个单词(单词只有小写字母组成,并且不会有重复的单词出现),现在老师要他在这本字典中查找出以某个字符串为前缀的单词的数量(单词本身也是自己的前缀)。
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是字典里的单词,一个空行代表单词表的结束。。第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串&＃xff08;长度不超过10&＃xff09;。

注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,输出以该字符串为前缀的单词的数量.
Sample Input
Raw
banana
band
bee
absolute
acm

ba
b
band
abc
Sample Output
Raw
2
3
1
0
Hint
简单字典树。。
Tags
————————————————————————————————————————————————————————
解题思路&＃xff1a;
就是一个简单的字典树&＃xff0c;对每个节点统计下面的子节点个数&＃xff0c;注意输入时一个空行结束。

#include
#include
#include
using namespace std;
const int MAX_NODE &＃61; 1000000 &＃43; 10;
const int CHARSET &＃61; 26;
int trie[MAX_NODE][CHARSET] &＃61; {0};
int sum[MAX_NODE] &＃61; {0};
int k &＃61; 1;void insert_tree(char *str){//建树int len &＃61; strlen(str);int p &＃61; 0;for(int i&＃61;0; i<len; i&＃43;&＃43;){int c &＃61; str[i] - &＃39;a&＃39;;if(!trie[p][c]){trie[p][c] &＃61; k;k&＃43;&＃43;;}p &＃61; trie[p][c];sum[p]&＃43;&＃43;;}
}int search_tree(char *str){//查询int len &＃61; strlen(str);int p &＃61; 0;for(int i&＃61;0; i<len; i&＃43;&＃43;){int c &＃61; str[i] - &＃39;a&＃39;;if(!trie[p][c]) return 0;p &＃61; trie[p][c];}return sum[p];
}int main(){char str[20];while (gets(str) && strlen(str)) {insert_tree(str);}while (gets(str))printf("%d\n", search_tree(str));return 0;
}