poj_2503 Babelfish(ELF哈希)_christry_stool的博客-程序员秘密

Babelfish
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 41750   Accepted: 17700

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.

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.

查词典题,不过我因为把手误把 int 打成 char WA了几次。。
字符串哈希用ELFHash会快上很多,至少是我自己写的哈希的两倍快。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stack>
#include <bitset>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#define FOP freopen("data.txt","r",stdin)
#define inf 0x3f3f3f3f
#define maxn 1000010
#define mod 1000007
#define PI acos(-1.0)
#define LL long long
using namespace std;

struct Node
{
    int pos;
    int next;
}node[maxn];

int cot;
int hashTable[maxn];

int n = 0;
char word[100010][12];
char vals[100010][12];

void initHash()
{
    cot = 0;
    memset(hashTable, -1, sizeof(hashTable));
}

bool cmp(char *a, char *b)
{
    return strcmp(a, b) == 0;
}

int getHash(char *a)
{
    int res = 0;
    for(int i = 0; a[i] != '\0'; i++) res += a[i] * (i+1);
    return res % mod;
}

int ELFHash(char *key)
{
    unsigned long h = 0;
    while(*key)
    {
        h = (h<<4) + (*key++);
        unsigned long g = h&0Xf0000000L;
        if(g) h ^= g>>24;
        h &= ~g;
    }
    return h%mod;
}

void insertHash(char *val, int pos)
{
    node[cot].pos = pos;
    //int key = getHash(val);
    int key = ELFHash(val);
    node[cot].next = hashTable[key];
    hashTable[key] = cot++;
}

int searchHash(char *val)
{
    //int key = getHash(val);
    int key = ELFHash(val);
    int next = hashTable[key];
    while(next != -1)
    {
        int t =  node[next].pos;
        if(cmp(val, vals[t])) return t;
        next = node[next].next;
    }
    return -1;
}


int main()
{
    //FOP;
    initHash();
    char c[100];
    char val[12];

    while(gets(c) && c[0] != '\0')
    {
        sscanf(c, "%s %s", word[n], vals[n]);
        insertHash(vals[n], n);
        n++;
    }

    while(~scanf("%s", val))
    {
        int t = searchHash(val);
        if(t != -1) printf("%s\n", word[t]);
        else printf("eh\n");
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/christry_stool/article/details/53012811

智能推荐

vue配合iview,render使用_dianlupeng4187的博客-程序员秘密

//循环数据添加div(点击事件)render: (h, params) =&gt; {//h,表示当前的元素,params表示获取的接口的数据,params.row获取数据中的行的数据,params.row.isMessageCompletion获取数据中的行数据中的isMessageCompletion这个表格的数据return h('div', {//此时h表示divs...

HandyControl:重写原生样式,包含 70余款自定义控件的WPF控件库_handycontrol 示例_Gitee的博客-程序员秘密

Gitee 此前为大家介绍过一款优质的 WPF 控件库,受到了很多 C# 开发者的欢迎,由此可见Windows 开发者的基数仍然很高。今天为大家推荐的就是另一款在 Gitee 上很受欢迎的 WPF 控件库。项目名称:HandyControl项目作者:HandyOrg开源许可协议:MIT项目地址:https://gitee.com/handyorg/HandyControl项目简介HandyControl 是一套 WPF 控件库,它几乎重写了所有原生样式,同时包含 70 余款自定.

你大概走了假敏捷:认真说说敏捷的实现和问题(手绘版)_Eric.Liang的博客-程序员秘密

转载自:https://cloud.tencent.com/developer/article/1004881 今天你敏捷了没有?“敏捷”在互联网和软件开发领域从涓涓细流逐渐演变为行业潮流,往小了说是改进了开发方法,往大了说是革了瀑布流式的命——把产品开发引向了快速迭代、小步快跑的路线上。 我们使用 tapd 写 feature,流转、跟踪任务,言必谈敏捷,然而我们是否真的走对了敏...

自定制ProgressView_GofeyLee的博客-程序员秘密

苹果原生的progressView高度不可变,用起来很是不方便,说不定以后用的到,别人说不定也用的到,还是自己写一个。下边是主要的代码,详细的代码可以参考https://github.com/gofey/LittleDemos自定义ProgressView这一项闲话不说,都是比较基础的代码,都能看得懂我是自定制的一个View重新initWithFrame方法- (ins

吃馅饼 学口语_Ejnstein的博客-程序员秘密

 这里说的馅饼就是老外口中的pie,和我们的馅饼不同的是,他们的是烤出来的,我们的是烙出来的。Pie是英国人和美国人爱吃爱做的点心,因而也派生出数条习语。as easy as pie这条习语起源于吃馅饼时那种“舒适和享受”(ease and enjoyment),不过,在比喻义中,easy的意思转变成“容易”,比如:The examination was as easy as pie.

点云(一):PCL环境配置 - WIN10+VS2015+PCL1.8.0+Cmake+OpenCV+Python_pcl1.8 cmake_isabel1997的博客-程序员秘密

一、下载文件PCL下载-百度云链接:https://pan.baidu.com/s/1gL-thPQIpuwUljAC7mLBkw 提取码:obx4包含文件:pcl-1.8.0-pdb-msvc2015-win64,pcl-1.8.0-pdb-msvc2015-win64注意:所下载的PCL文件一定要与VS版本对应,例如该文件中的msvc2015对应VS2015版本VS2015官网下载即可...

随便推点

build vocab_build_vocab_sinat_15355869的博客-程序员秘密

&quot;&quot;&quot;Build vocabularies of words and tags from datasets&quot;&quot;&quot;import argparsefrom collections import Counterimport jsonimport osparser = argparse.ArgumentParser()parser.add_argument('--min_count_w...

ITK 基于特征的血管提取01_血管特征提取_zhimingf的博客-程序员秘密

ITK的血管提取的方法主要来自于文章:Three-dimensional multi-scale line filter for segmentation and visualization of curvilinear structures in medical images。文章的大体思路是构造一个3D线性的血管滤波器,用于过滤噪声,保留血管结构。首先介绍几个概念:一阶导和二阶导。

在pycharm中matlab画函数图,PyCharm无法正确打开matplotlib绘图_weixin_39874809的博客-程序员秘密

我对PyCharm和matplotlib有一个问题,我似乎无法纠正。当我使用PyCharm和ipython作为解释命令的控制台时,在保存图形之前不会显示绘图。然而,当我试图从外面的皮查姆阴谋时,这并没有发生。以下是PyCharm中失败的exmaple过程:In[2]: import matplotlib.pyplot as pltBackend MacOSX is interactive back...

前端jQuery之事件流_daruan1111的博客-程序员秘密

1.事件流概念  描述的是从页面中接收事件的顺序  包含事件捕获阶段,处于目标阶段,事件冒泡阶段2.绑定事件语法bind(type,data,fn)示例:每个标签被点击的时候,弹出其文本$("p").bind("click", function(){ alert( $(this).text() );});3.解绑事件unb...

CSS;HTML;JAVASCRIPT面试题_weixin_30648587的博客-程序员秘密

面试题专区:1.apply()和call()的区别?答:call()和apply()的作用只主要是改变this的指向;他们的区别在于参数转递给函数call():使用自有的实参列表作为函数的参数;apply():要求以数组的形式转入参数;2.解释 css sprite,如何使用----(雪碧图)定义:它允许你将一个页面涉及到的所有零星图片都包含到一张...