vua 10282 - Babelfish（Hash、map）

本文主要是介绍vua 10282 - Babelfish（Hash、map），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

题意：100000个字的字典。

1、直接用STL中的map 0.532sAC

2、Hash 0.115sAC

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
int const MAX_SIZE = 11, MAX_N = 100000;
map<string,string> dict;void print(string s)
{if(dict.find(s) != dict.end())cout << dict[s] << endl;else cout << "eh" << endl;
}int main()
{string s1, s2;while(cin >> s1 && cin.peek()!='\n'){cin >> s2;dict[s2] = s1;}print(s1);while(cin >> s1)print(s1);return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int const MAX_SIZE = 11, MAX_N = 100000, MAX_HASH = 100003;
int n;
char s1[MAX_N][MAX_SIZE], s2[MAX_N][MAX_SIZE];
int head[MAX_HASH], nextu[MAX_HASH];void init_lookup_tabel(){ memset(head, 0, sizeof(head));}int get_hash(char *s)
{int seed = 131;int hash = 0;while(*s)hash = hash * seed + *s++;return (hash & 0x7fffffff) % MAX_HASH;
}int find(char *s)
{int hash = get_hash(s);int u = head[hash];while(u){if(!strcmp(s2[u], s))return u;u = nextu[u];}return -1;
}void try_to_insert(int i)
{int hash = get_hash(s2[i]);nextu[i] = head[hash];head[hash] = i;
}void print(char *s)
{int i = find(s);if(i != -1)printf("%s\n", s1[i]);else printf("eh\n");
}int main()
{n = 1;char ss1[MAX_SIZE], ss2[MAX_SIZE];while(scanf("%s", ss1) && cin.peek()!= '\n'){scanf("%s", ss2);strcpy(s1[n], ss1);strcpy(s2[n], ss2);try_to_insert(n++);}print(ss1);while(scanf("%s", ss1) != EOF)print(ss1);return 0;
}

这篇关于vua 10282 - Babelfish（Hash、map）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---