题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1251
Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input 输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output 对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input banana band bee absolute acm
ba b band abc
Sample Output 2 3 1 0
就是很入门的字典树 难度， 但是 杭电 g++提交会 Memory Limit Exceeded 还是问了 同学的 说用 c++交 就没事了 。但是万能的 #include <bits/stdc++.h>竟然不让用
代码:
#include <iostream> #include <cstdio> #include <string.h> //#include <bits/stdc++.h> using namespace std; struct node { int t; node *child[27]; node() { t=1; for (int i=0; i<27; i++) { child[i]=NULL; } } }; node * root; void build(char *a) { node *p, *newnode; int i; p = root; for (i=0; i<strlen(a); i++) { int m = a[i]-'a'; if (p->child[m]!=NULL) { p->child[m]->t++; //cout<<p->child[m]->t++<<endl; p = p->child[m]; continue; } else { newnode = new node; p->child[m] = newnode; p = newnode; } } } int finded(char *b) { node *p, *newnode; int i; p = root; for (i=0; i<strlen(b); i++) { int m = b[i]-'a'; p = p->child[m]; if (p==NULL) return 0; } return p->t; } int main() { char a[10]; root = new node; while(gets(a)) { if (a[0]=='\0') break; build(a); } char b[10]; while (scanf("%s",b)!=EOF) { int ans = finded(b); cout<<ans<<endl; } return 0; }map写法
#include <iostream> #include <bits/stdc++.h> using namespace std; int main() { char a; string sum=""; map<string, int>st; while (1) { scanf("%c",&a); if (a=='\n') { scanf("%c",&a); sum=""; } if (a=='\n') { break; } sum+=a; st[sum]++; } while (cin>>sum) cout<<st[sum]<<endl; return 0; }em。。。。。。。。杭电题 拉到比赛里面 指针写的字典树 内存超限。 来个数组写的
#include <iostream> #include <string.h> #include <cstdio> #include <bits/stdc++.h> using namespace std; int tree[1000010][26]; int num[1000010]; int t = 1; void Insert(char a[]) { int i; int c=0; for (i=0; a[i]; i++) { int n = a[i]-'a'; if (tree[c][n]==0) //改串没有存入字典树 { tree[c][n] = t++; } c = tree[c][n]; num[c]++; } } int Find(char a[]) { int i; int c=0; for (i=0; a[i]; i++) { int n = a[i]-'a'; if (tree[c][n]==0) { return 0; } c = tree[c][n]; } return num[c]; } int main() { char a[11]; while(gets(a)) { if (a[0]==NULL) //空行。gets读入的回车符会自动转换为NULL。 { break; } Insert(a); } while (gets(a)) { printf ("%d\n",Find(a)); } return 0; }