生活随笔
收集整理的這篇文章主要介紹了
NYOJ 685 查找字符串(map)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
查找字符串
時間限制：
1000?ms ?|? 內(nèi)存限制：
65535?KB 難度：
3
描述
小明得到了一張寫有奇怪字符串的紙，他想知道一些字符串出現(xiàn)了多少次，但這些字符串太多了，他想找你幫忙，你能幫他嗎？輸入字符包括所有小寫字母、‘@’、‘+’。
輸入第一行包含一個整數(shù)T（T<=100).表示測試數(shù)據(jù)組數(shù)。
接下來每組數(shù)據(jù)第一行包含兩個整數(shù)n，m(n，m<100000),分別表示有n個字符串，小明要問你m次。
接下來n行，每行包含一個字符串，長度不大于15。
接下來m行，每行包含一個字符串，表示小明要問該串出現(xiàn)的次數(shù)。
輸出輸出每組小明詢問數(shù)串出現(xiàn)的次數(shù)。樣例輸入 1 5 3 hello it@is+so@easy hello ibelieveicanac hello hello icannotacit Giveup 樣例輸出 3 0 0 調(diào)用C++庫函數(shù)map，問題會更容易求解一點(diǎn)！ 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;
}
優(yōu)秀代碼：
#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));}}
}
總結(jié)
以上是生活随笔為你收集整理的NYOJ 685 查找字符串(map)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
