☘前言☘
今日份水题开始。希望有想要提高的同学跟我们一起来刷题0.0
P3370 【模板】字符串哈希
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
解题思路
📑写在最后
P1540 [NOIP2010 提高组] 机器翻译
解题思路
随手写一个链式hash就好了，需要注意的是，内存，内存，内存！！！！c语言的精华就是内存管理，我就是个菜鸡。。。记录字符串用于比较的时候一定要新开一端区域，不然的话就是错的！！！！
#include <cstdio> #include <cstring> #include <cstdlib> const int maxn = 49999; int count = 0; struct node{ char *s; node *next; }; node * HashTable[maxn]; void HashInsert(char *str){ int hashnum = 0,n = 0; for(int i = 0;str[i];++i){ hashnum *= 128; hashnum += str[i]; hashnum %= maxn; ++n; } node *p = HashTable[hashnum]; while(p){ if(strcmp(p->s,str) == 0) return; p = p->next; } ++count; p = (node *)malloc(sizeof(node));//头插法 char *tmp = (char *)malloc(sizeof(char) * (n + 1)); memset(tmp,0,n+1); strcpy(tmp,str); p->s = tmp; p->next = HashTable[hashnum]; HashTable[hashnum] = p; } int main(){ int n; scanf("%d", &n); count = 0; memset(HashTable,0,sizeof(HashTable)); while(n--){ char s[1509]; scanf("%s",s); HashInsert(s); } printf("%d\n",count); return 0; }
