简单字典树 这是我初次接触字典树,代码的效率还不是很高,有什么建议,敬请指教
题目:
统计难题
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
下面直接贴代码1 C:
#include<stdio.h>
#include<stdlib.h>#include<string.h>#define max 26typedef struct t_node //字典树结点信息{ struct t_node * next[max]; int count;}t_node;t_node * root;void insert(char * str) //在字典树中新增子树{ int i, index, len; t_node * current, * newnode; len = strlen(str); if(len == 0) return ; current = root; for(i = 0; i < len; i ++) { index = str[i] - 'a'; //寻找对应的子树进行插入 if(current->next[index] != NULL) //如果有该结点,继续 { current = current->next[index]; (current->count) ++; } else //如果没有,新增结点 { newnode = (t_node *) calloc(1, sizeof(t_node)); current->next[index] = newnode; current = newnode; current->count = 1; } }}int find(char * str) //查看与str对应的前缀的数目
{ int i, index, len; t_node * current = NULL; len = strlen(str); if(len == 0) return 0; current = root; for(i = 0; i < len; i ++) { index = str[i] - 'a'; if(current->next[index] != NULL) //如果有相应结点,继续 current = current->next[index]; else //如果没有相应结点,返回0 return 0; } return current->count;}int main()
{ char str[11]; root = (t_node *) calloc(1, sizeof(t_node)); while(gets(str) && strcmp(str, "") != 0) { insert(str); } while(scanf("%s", str) != EOF) { printf("%d\n", find(str)); } return 0;}
代码2 STL:968Ms
#include<iostream>
#include<map>#include<string>using namespace std;int main(){ int i, len; char str[11]; map<string, int > m; while(gets(str)) { len = strlen(str); if(len == 0) break; for(i = len; i >= 1; i --) { str[i] = '\0'; m[str] ++; } } while(gets(str)) { cout << m[str] << endl; } return 0;}