统计难题
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 131070/65535K (Java/Other)
Total Submission(s) : 92 Accepted Submission(s) : 20
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acmba b band abc
Sample Output
2 3 1 0
Author
Ignatius.L
此题也是基础的字典树问题，在这里，我用两种方法给大家呈现
第一种：指针实现。
指针实现的字典树最大的优点就是从代码上来看，形象且浅显易懂，但由于大量的空指针存在，可能从内存的角度讲，不是很好（在OJ problem里此题交指针是能过的，但在Web DIV里同样交此题就会出现爆内存的情况）
#include <iostream>//指针实现
#include <cstdio>
#include <cstring>
using namespace std;
char str[11];
struct node
{node *next[26];int cnt;node(){//构造函数，创建结点时自动执行cnt=0;for(int i=0; i<26; i++)next[i] = NULL;//将该节点的下面的26个节点初始化为空}
};
void insert(node *p,char *str)
{for(int i=0; str[i]; i++){int t=str[i]-'a';if(p->next[t] == NULL)p->next[t] = new node;//如果节点不存在，那么先new一个p = p->next[t];p->cnt++;}
}
int find(node *p,char *str)
{for(int i=0; str[i]; i++){int t=str[i]-'a';p = p->next[t];if(!p) return 0;}return p->cnt;
}
int main()
{node *root=new node();while(gets(str)&&strlen(str))insert(root,str);while(gets(str)){int ans=find(root,str);printf("%d\n",ans);}return 0;
}第二种：数组模拟实现。
数组模拟实现的优点自然是从内存角度讲比较节省空间，但是初学者可能看到数组模拟的代码比较茫然，不知道是如何实现的，请大家多点耐心，务必学会这种方法。
#include <cstdio>//数组模拟实现
#include <cstring>
#define N 5000000
using namespace std;
int tree[N][26],cnt[N];
char str[20];
int tot;
void insertTrie(char *str)
{int len=strlen(str);int now=0;for(int i=0; i<len; i++){int w=str[i]-'a';if(tree[now][w] == 0) tree[now][w] = ++tot;now = tree[now][w];cnt[now]++;}
}
int searchTrie(char *str)
{int len=strlen(str);int now=0;for(int i=0; i<len; i++){int w=str[i]-'a';if(tree[now][w] == 0) return 0;now = tree[now][w];}return cnt[now];
}
int main()
{while(gets(str)&&strcmp(str,"")!=0)insertTrie(str);while(gets(str))printf("%d\n",searchTrie(str));return 0;
}