【4.10日题解】——字符串哈希

☘前言☘

今日份水题开始。

希望有想要提高的同学跟我们一起来刷题0.0
P3370 【模板】字符串哈希

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min

---

全文目录

• ☘前言☘
• 解题思路
• 📑写在最后

---

P1540 [NOIP2010 提高组] 机器翻译

解题思路

随手写一个链式hash就好了，需要注意的是，内存，内存，内存！！！！c语言的精华就是内存管理，我就是个菜鸡。

。

。

记录字符串用于比较的时候一定要新开一端区域，不然的话就是错的！！！！

#include 
#include 
#include 

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;

}

📑写在最后

今天就这样，明日再见0.0打周赛了，力扣来不来0.0