poj-2503

水题， 但是，在malloc之后，我忘记了memsetet 0, 结果 几次WA... (因为这次hash。 成员有字符串数组，不能保证全员覆盖，比如 申请长度为15，只有一个长度为10的memcpy字符串，所以第11个字符不能保证是结束符，所以所有初始字符都需要为0)，这实际上是常识...

#include <stdio.h>  #include <string.h>  #include <malloc.h>  #include <iostream>  #include <map>  #include <string>  using namespace std;  struct dict_entry{      int hval;      char foreign[15];      char local[15];      struct dict_entry * next;  };  const int MAXH = 999999;  typedef struct dict_entry dict_entry;  dict_entry * dict[MAXH];  map<string, string> dictMap;  int hash(char * word) {      long step = 1;      long acc = 0;      while(*word) {          // acc += (*word) * step;          // step *= 10;          acc += (*word) * (*word);          word++;      }      return acc%MAXH;  }  void fillInHash(char * local, char * foreign) {      // printf("fillInHash %s %s\n", local, foreign);      int havl = hash(foreign);      dict_entry * prev = dict[havl];      dict_entry * new_entrty = (dict_entry *)malloc(sizeof(dict_entry));      dict[havl] = new_entrty;      new_entrty->next = prev;      new_entrty->hval = havl;      // printf("memcpy foreign %d\n", (int)strlen(foreign));      memcpy(new_entrty->foreign, foreign, strlen(foreign));      // printf("memcpy local %d\n", (int)strlen(local));      memcpy(new_entrty->local, local, strlen(local));  }  const char * translate(char * foreign) {      int havl = hash(foreign);      dict_entry * search = dict[havl];      while (search) {          if (!strcmp(foreign, search->foreign)) {              return search->local;          }          search = search->next;      }      return "eh";  }  int main() {      dictMap.clear();      memset(dict, 0, sizeof(dict));      char line[30] = "";      char foreign[15] = "";      char local[15] = "";            while(cin.getline(line, sizeof(line)) && line[0]!='\0')      {          sscanf(line,"%s %s", local ,foreign);          // fillInHash(local , foreign);          dictMap[string(foreign)] = string(local);      }      char translated[15] = "";      while(cin.getline(translated, sizeof(line)) && translated[0]!='\0')      {          map<string, string>::iterator it;          it = dictMap.find(string(translated));          if (it == dictMap.end()) {              printf("eh\n");          } else {              printf("%s\n", dictMap[string(translated)].c_str());          }      } }

比较自己的hash和直接使用STL的性能差异， 拉链法:

C++

454MS(hash函数使用ELFhash，一个NB字符串hash法)

547MS(hash函数使用简单的hash，每个字母的平方和)

875MS （STL MAP， 虽然慢，但空间没那么大)

值得一提的是，本题输入以空格结束判断， 方法比较取巧， 以前使用sscanf的机会很少.