首页 > 代码库 > NYOJ 685 查找字符串(map)
NYOJ 685 查找字符串(map)
查找字符串
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
小明得到了一张写有奇怪字符串的纸,他想知道一些字符串出现了多少次,但这些字符串太多了,他想找你帮忙,你能帮他吗?输入字符包括所有小写字母、‘@’、‘+’。
- 输入
- 第一行包含一个整数T(T<=100).表示测试数据组数。
接下来每组数据第一行包含两个整数n,m(n,m<100000),分别表示有n个字符串,小明要问你m次。
接下来n行,每行包含一个字符串,长度不大于15。
接下来m行,每行包含一个字符串,表示小明要问该串出现的次数。 - 输出
- 输出每组小明询问数串出现的次数。
- 样例输入
1
5 3
hello
it@is+so@easy
hello
ibelieveicanac
hello
hello
icannotacit
Giveup
- 样例输出
3
0
0
调用C++库函数map,问题会更容易求解一点!
AC码:
#include<iostream> #include<string> #include<cstdio> #include<map> using namespace std; int main() { int T,i,n,m; char str[15]; scanf("%d",&T); while(T--) { map<string,int> word_count; scanf("%d%d",&n,&m); getchar(); for(i=0;i<n;i++) { scanf("%s",str); ++word_count[str]; } for(i=0;i<m;i++) { scanf("%s",str); printf("%d\n",word_count[str]); } } return 0; }
优秀代码:#include<stdio.h> #include<string.h> #include<stdlib.h> struct node { int sum; struct node *next[80]; }; struct node *root; int s[20]; node* build() { struct node *p=(node *)malloc(sizeof(node)); p->sum=0; for(int i=0;i<80;i++) { p->next[i]=NULL; } return p; } int insert(char*s) { //struct node *root=(struct node*)malloc(sizeof(struct node)); struct node *p=root; int l=strlen(s); for(int i=0;i<l;i++) { if(p->next[s[i]-‘+‘]!=NULL) { p=p->next[s[i]-‘+‘]; } else { p->next[s[i]-‘+‘]=build(); p=p->next[s[i]-‘+‘]; } } return p->sum++; } int search(char *s) { int l=strlen(s); struct node *p=root; for(int i=0;i<l;i++) { if(p->next[s[i]-‘+‘]!=NULL) p=p->next[s[i]-‘+‘]; else return 0; } return p->sum; } int main() { int n,a,b; char str[20],q[20]; scanf("%d",&n); while(n--) {root=build(); scanf("%d%d",&a,&b); getchar(); for(int i=0;i<a;i++) { gets(str); insert(str); } for(int i=0;i<b;i++) { gets(q); printf("%d\n",search(q)); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。