poj2503 Babelfish
IAmL
posted @ 2009年4月03日 05:25
in 解题报告
with tags
poj2503 Babelfish解题报告
, 3041 阅读
很郁闷,在这样的水题上耗费了将近3个小时~看来我还是太水了~。这题基本上没什么技术含量,唯一一个难点不是算法,而是读入(主要是判断空行……)。之后把读入的两个数组放在hash中。这里用的hash函数是常用的ELFhash,虽然说这个函数能极大地避免重复映射,但是还是存在冲突的可能性,所以要注意写上冲突后的处理方法。之后就是读入要查找的字符串,然后在hash中查找(我就是这部分写得不够好,导致调试了n久……)
后记:
1.本题除了用hash,还能用排序+二分搜索来写。(当然速度上就肯定比不上hash啦)
2.可以粗暴地用map来做。但是这样一来这题就成为真正的水题了……
========不华丽的分割线===========
#include <iostream>
using namespace std;
#define N 100001
#define strSize 15
struct hash
{
bool used;
char fo[strSize], en[strSize];
hash *next;
hash(){used = false; next = NULL;}
hash(char *f, char *e)
{
int i = 0;
while (*f) fo[i++] = *f++;
fo[i] = 0;//设置字符设串的结束标志
i = 0;
while (*e) en[i++] = *e++;
en[i] = 0;
used = false;
next = NULL;
}
}h[N];
int ELFhash(char *key)
{
unsigned long g, h = 0;
while (*key)
{
h = (h << 4) + *key++;
g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h % N;
}
int main()
{
char *c1, *c2, tmp, en[strSize], fo[strSize];
hash *p;
bool found;
int key, i;
while (1)
{
tmp = getchar();
if (tmp == '\n') break;//判断是否是空行
en[0] = tmp;
scanf("%s%s", en + 1, fo);
tmp = getchar();
key = ELFhash(fo);
if (!h[key].used)
{
h[key].used = true;
i = 0;
c1 = en;
while (*c1) h[key].en[i++] = *c1++;
en[i] = 0;
c1 = fo;
i = 0;
while (*c1) h[key].fo[i++] = *c1++;
fo[i] = 0;
}
else//处理重复冲突的情况
{
p = &h[key];
while (p->next != NULL) p = p->next;
p->next = new hash(fo, en);
}
}
while (scanf("%s", fo) != EOF)
{
key = ELFhash(fo);
if (!h[key].used) printf("eh\n");
else
{
p = &h[key];
while (p != NULL)
{
found = true;
c1 = fo;
c2 = p->fo;
while (*c1 && *c2)//判断字符窗是否相等
{
if (*c1++ != *c2++)
{
found = false;
break;
}
}
if (found && !(*c1) && !(*c2))
{
printf("%s\n", p->en);
break;
}
p = p->next;
}
if (p == NULL) printf("eh\n");
}
}
return 0;
}
using namespace std;
#define N 100001
#define strSize 15
struct hash
{
bool used;
char fo[strSize], en[strSize];
hash *next;
hash(){used = false; next = NULL;}
hash(char *f, char *e)
{
int i = 0;
while (*f) fo[i++] = *f++;
fo[i] = 0;//设置字符设串的结束标志
i = 0;
while (*e) en[i++] = *e++;
en[i] = 0;
used = false;
next = NULL;
}
}h[N];
int ELFhash(char *key)
{
unsigned long g, h = 0;
while (*key)
{
h = (h << 4) + *key++;
g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h % N;
}
int main()
{
char *c1, *c2, tmp, en[strSize], fo[strSize];
hash *p;
bool found;
int key, i;
while (1)
{
tmp = getchar();
if (tmp == '\n') break;//判断是否是空行
en[0] = tmp;
scanf("%s%s", en + 1, fo);
tmp = getchar();
key = ELFhash(fo);
if (!h[key].used)
{
h[key].used = true;
i = 0;
c1 = en;
while (*c1) h[key].en[i++] = *c1++;
en[i] = 0;
c1 = fo;
i = 0;
while (*c1) h[key].fo[i++] = *c1++;
fo[i] = 0;
}
else//处理重复冲突的情况
{
p = &h[key];
while (p->next != NULL) p = p->next;
p->next = new hash(fo, en);
}
}
while (scanf("%s", fo) != EOF)
{
key = ELFhash(fo);
if (!h[key].used) printf("eh\n");
else
{
p = &h[key];
while (p != NULL)
{
found = true;
c1 = fo;
c2 = p->fo;
while (*c1 && *c2)//判断字符窗是否相等
{
if (*c1++ != *c2++)
{
found = false;
break;
}
}
if (found && !(*c1) && !(*c2))
{
printf("%s\n", p->en);
break;
}
p = p->next;
}
if (p == NULL) printf("eh\n");
}
}
return 0;
}