poj 2503 哈希 Map 字典树
2024-10-01 19:58:59
Babelfish
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 36967 | Accepted: 15749 |
Description
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language
word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.
word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.
Output
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
Hint
Huge input and output,scanf and printf are recommended.
Source
//16096K 2625MS
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring> using namespace std; int main()
{
char s[100],s1[11];
string ss;
char c;
map<string,string>Q;
int num;
while(gets(s)&&s[0]!='\0') //读串比读多个字符快
{
int len=strlen(s);
int i;
for( i=0;i<len;i++)
{
if(s[i]==' ')
{s[i]='\0';
break;
}
}
ss=s+i+1;
Q[ss]=s;
}
while(~scanf("%s",s1))
{
if(Q[s1].size())
cout<<Q[s1]<<endl;
else
printf("eh\n");
}
}
// while(~scanf("%c",&c)) // 超时
// {
// if(c=='\n')
// break;
// num=0;
// while(c!=' ')
// {
// s[num++]=c;
// scanf("%c",&c);
// }
// s[num]='\0'; //够成字符串
// num=0;
// scanf("%c",&c); //防止上一个空格被读入
//
// while(c!='\n')
// {
// ss[num++]=c;
// scanf("%c",&c);
// }
// ss[num]='\0';
// Q[ss]=s;
// }
//字典树 26240K <span id="transmark"></span>735MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib> using namespace std; char ss[100],s[100],c[100010][100];
int num=0;
struct node
{
int flag;
node *next[26];
}*head;
node * Creat()
{
node *p;
p=new node;
p->flag=0;
for(int i=0;i<26;i++)
p->next[i]=NULL;
return p;
}
int Build_Tree()
{
node *p=head;
int len=strlen(s);
for(int i=0;i<len;i++)
{
int a=s[i]-'a';
if(!p->next[a])
{
p->next[a]=Creat();
//p->next[a]->flag=num;
}
p=p->next[a];
}
p->flag=num;
}
int Find(char s1[])
{
int len=strlen(s1);
node *p=head;
for(int i=0;i<len;i++)
{
int a=s1[i]-'a';
if(!p->next[a])
{
return 0;
}
p=p->next[a];
}
return p->flag;
}
int main()
{
num=1;
head=Creat();
while(gets(ss)&&ss[0]!='\0')
{
sscanf(ss,"%s %s",c[num],s);
Build_Tree();
num++;
}
char s1[100];
while(~scanf("%s",s1))
{
int flag=Find(s1);
//cout<<flag;
if(flag)
printf("%s\n",c[flag]);
else
printf("eh\n");
}
}
最新文章
- win10使用技巧之如何打出偏僻字母
- SVM-非线性支持向量机及SMO算法
- Xcode开发技巧之Code Snippets Library
- QT笔记之VS开发程序遇到的问题
- HDU-4522 湫湫系列故事——过年回家 最短路
- Spark Idea Maven 开发环境搭建
- Groupon面经Prepare: Max Cycle Length
- [转] 苹果所有常用证书,appID,Provisioning Profiles配置说明及制作图文
- [Raobin] Ext.net在前端直接将对象转为json形式传入后台
- 【OpenCV学习笔记】之六 手写图像旋转函数---万丈高楼平地起
- 手把手教你DIY一个春运迁徙图(一)
- Android build-tools升级到23.0.0_rc1无法解决编译后的问题
- java equals和==区别及string类的说明
- acure使用
- unity打包安卓应用及生成签名
- tomcat 取消项目名访问路径
- 整数划分 NBUT - 1046
- 使用requests库提交multipart/form-data 格式的请求
- P3507 GRA-The Minima Game
- Python自动发邮件——smtplib和email库和yagmail库
热门文章
- 题解 CF1027D 【Mouse Hunt】
- HN0I2000最优乘车 (最短路变形)
- 绿色版SecureCRT启动崩溃,遇到一个致命的错误且必须关闭
- java无依赖读取Excel文件
- POJ 3150 Cellular Automaton(矩阵高速幂)
- hdoj--1034--Hidden String(dfs)
- Vsftp权限控制(持续增加中)
- 《读书报告 – Elasticsearch入门 》----Part II 深入搜索(2)
- Nginx 代理以及HTTPS (二)
- mysql-5.6.15 开启二进制文件