poj2503 二分查找字符串-白红宇

poj2503 二分查找字符串

阅读量：4205 次

发布时间：2019-05-26

本文共 1781 字，大约阅读时间需要 5 分钟。

Babelfish（poj 2503）

你刚刚从滑铁卢搬到一个大城市里面，这个城市里的人们都讲着外文都带着很令人费解的方言。不过很幸运，你有本字典可以帮助你理解这些话语。

输入：

输入包括100,000个字典条目，紧接着是一个空行，然后便是等待你翻译的消息，每个消息中的单词数目最多不超过100,000。每一个字典条目都只有一行，包括一个英文单词和一个外文单词，中间用个空格分隔。不会在字典中出现两个相同的外文单词。每一个消息都是由一系列的外文单词构成，每个单词占一行，单词最多不会超过10个小写字母。

输出：

输出翻译成英文的消息，每行一个单词，字典中没出现的单词需要翻译成“eh”。

输入样例：

dog ogday

cat atcay

pig igpay

froot ootfray

loops oopslay

atcay

ittenkay

oopslay

输出样例：

cat

loops

#include
   
    #include
    #include
     
      #include
      
       using namespace std;int main(){    char str[20];    char a[10],b[10];    map
       
        mp;    string s;    while(gets(str)&&str[0]!=0)    {        sscanf(str,"%s %s",a,b);        mp[b] = a;    }    while(cin>>s)    {        if(mp[s].size())            cout<
        
         <

////  main.cpp//  二分////  Created by liuzhe on 16/6/1.//  Copyright © 2016年 my_code. All rights reserved.//#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;//poj 2503 二分const int mm=100010;class node{public: ///记录字典 char e[60],s[60];}dic[mm];///需要翻译的单词char t[60];int pos;bool cmp(node a,node b){ return strcmp(a.s,b.s)<0;}///二分查找翻译的单词位置，查不到说明是外文int binserch(char*s){ int l=0,r=pos-1; while(l<=r) { int mid=(l+r)/2; if(strcmp(dic[mid].s,s)==0)return mid; else if(strcmp(dic[mid].s,s)>0)r=mid-1; else l=mid+1; } return -1;}int main(){ pos=0;///字典中单词的个数 char z; while(scanf("%s%c",dic[pos].e,&z)!=EOF) { ///如果取到中间是\n说明字典已经读入完 ///并读入了一个需要查找的单词 if(z=='\n') { strcpy(t,dic[pos].e);break; } scanf("%s",dic[pos++].s); } ///排序 sort(dic,dic+pos,cmp); int num=binserch(t); if(num>=0) printf("%s\n",dic[num].e); else puts("eh"); while(scanf("%s",t)!=EOF) { num=binserch(t); if(num>=0) printf("%s\n",dic[num].e); else puts("eh"); }}

转载地址：http://vsali.baihongyu.com/

你可能感兴趣的文章