题目链接：点击打开链接
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
题意：Trie树模板题，统计出现次数，注意注释
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;
const int maxn = 400000 + 20;
int tot;
char s[maxn];
int num[maxn] = {0};//前缀末尾编号为i的单词数量。
int trie[maxn][26];
//trie[i][j] = k表示编号为i的节点的第j个孩子（内容为j的孩子）是编号为k的节点
//编号为整棵树中的编号, 内容是值的编号,如小写字母的字典树中，'b'的编号为'b' - 'a' = 1;void insert(char s[]){//插入单词s int root = 0;//从整颗字典树的根节点开始找起，整颗字典树的根节点的编号为0 int len = strlen(s);for(int i = 0; i < len; i++){int id = s[i] - 'a';if(!trie[root][id]) trie[root][id] = tot++;//如果之前没有从root到id过，自己创建一个。//tot为整棵树中的编号，为全局变量，编到几就是几 root = trie[root][id];//无论从root到id的边是否之前存在，下一步都要往下走 num[root]++;//每次沿字典树输入一个单词，都让相应编号的num++，方便输出以某字符串为前缀的单词数 }
}int find(char s[]){ //前缀查找函数，注意：查找前缀是否存在与查找单词是否存在不同！//如：空字典树中插入apple , applese 存在前缀app,但是不存在单词app!//如果要查找单词，对应的insert函数要加入一个bool的v[i]标志：编号i的节点是单词结束的标志，find函数怎么改你懂的int root = 0;//依然是从根节点开始查找 int len = strlen(s);for(int i = 0; i < len; i++){int id = s[i] - 'a';if(!trie[root][id]) return 0;root = trie[root][id];}return num[root];}int main(){memset(trie, 0 , sizeof(trie));//初始化很重要tot = 1; //上面insert中为 tot++ , 所以这里应该初始化为1 while(gets(s)){//只有gets才能在遇到回车的时候返回长度为0的空串，gets同时也能记录空格 if(strcmp(s,"")==0) break;//学会此处的输入方法:若字符串长度为0或者输入的为空格,结束循环. //strcmp(str1, str2) 若str1 == str2返回0， 若前者字典序大，返回正数， 否则返回负数 insert(s);}//for(int i = 0; i < tot; i++)printf("num[%d]:%d\n", i, num[i]);//for(int i = 0; i < tot; i++)for(int j = 0; j < 26; j++) if(trie[i][j])printf("trie[%d][%c] = %d\n", i, j+'a', trie[i][j]);while(~scanf("%s",s)){printf("%d\n", find(s));}return 0;
}