NYOJ 685 查找字符串 - c++编程基础

TOP

NYOJ 685 查找字符串

2015-11-21 00:59:17 来源: 作者: 【大中小】浏览:2次

查找字符串

时间限制：1000 ms | 内存限制：65535 KB 难度：3

小明得到了一张写有奇怪字符串的纸，他想知道一些字符串出现了多少次，但这些字符串太多了，他想找你帮忙，你能帮他吗？输入字符包括所有小写字母、‘@’、‘+’。

15 3helloit@is+so@easyhelloibelieveicanachellohelloicannotacitGiveup

本题真是让我煞费苦心，，，那是一个恨啊，特别是指针覆盖问题。

解题思路：

为了锻炼C++容器的使用，我选择了使用map，基本的定义就是map p;这样，通过每次输入一个字符串，然后加入到map中统计，两类情况，map中已经存在该字符串，或者尚未存在，这只需加上ite==p.end()判断即可，做完之后提交发现LM，琢磨了下，觉得将cin换成scanf或者gets将会更加节省时间，于是乎，杯具开始了......

我很轻松的进行了相应改变，中间必须完全替换成char类型的字符串，不能和string混用，但遗憾的是出现了很奇怪的bug，找了好久，发现在使用指针类型作为map的属性的时候如果仍然只利用一个str字符串不断接受每一个输入，就会发生指针覆盖，也就是map存进去的字符串随着str的改变而变，郁闷啊.....之后定义大数组排除掉本问题。

不多说了，此外注意map的find()在未找到需要查找的值时指向p.end(),但本程序它似乎查找不到一个str，我郁闷半天，仔细思考下，觉得是不兼容指针型字符串的原因，便改成自己动手写了一个。其次，make_pair存入的数值将会insert到p.begin中而不是p.end()，切记。

end代码如下：

#include
  
   
#include
    #include
    
      using namespace std; char str[100005][20]; char s[20]; int main(){ int T,n,m; map 
     
      p; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); getchar(); p.clear(); map 
      
       ::iterator ite; while(n--){ gets(str[n]); for(ite=p.begin();ite!=p.end();ite++){ if(strcmp(ite->first,str[n])==0)break; } if(ite==p.end()){ p.insert(make_pair(str[n],1));ite=p.begin(); continue; } ite->second+=1; } while(m--){ gets(s); for(ite=p.begin();ite!=p.end();ite++){ if(strcmp(ite->first,s)==0)break; } if(ite==p.end()) printf("0\n"); else printf("%d\n",ite->second); } } return 0; }

LM代码

#include
  
   
#include
   
     #include
     #include
     
       #include
      
        using namespace std; int main(){ int T,n,m; string str; map 
       
        p; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); while(n--){ cin>>str; map 
        
         ::iterator ite; ite=p.begin(); ite=p.find(str); if(ite==p.end()){ p.insert(make_pair(str,1));continue; } if(str.compare(ite->first)==0){ ite->second+=1; } else { p.insert(make_pair(str,1)); } } while(m--){ cin>>str; map 
         
          ::iterator ite; ite=p.begin(); ite=p.find(str); if(ite==p.end()){ printf("0\n");continue; } if(str.compare(ite->first)==0){ printf("%d\n",ite->second); } } } return 0; }

描述
输入第一行包含一个整数T（T<=100).表示测试数据组数。 接下来每组数据第一行包含两个整数n，m(n，m<100000),分别表示有n个字符串，小明要问你m次。 接下来n行，每行包含一个字符串，长度不大于15。 接下来m行，每行包含一个字符串，表示小明要问该串出现的次数。
输出输出每组小明询问数串出现的次数。
样例输入
样例输出。。。。苦逼的程序员啊


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++实现Dijkstra算法	下一篇：codeforces 321E Ciel and Gondol..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: