首页 > 代码库 > 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));
        }
    }
}