想对字符串哈希，但一直错误

Question

想对字符串进行哈希，但一直错误，希望能帮忙解决，有完整代码在下面

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define Max 100
#define Maxsize 10
typedef char  datatype;
typedef struct Node {
    datatype data;
    struct Node* next;
}Node;
typedef struct head {
    struct Node arr[Maxsize];
}Hash;
int ZifuAscall(char ch[]) {//将字符转为ASCALL码的和
    int length = strlen(ch);
    int sum = 0, n = 0;
    for (int i = 0; i < length; i++) {
        n = (int)ch[i];
        sum = sum + n;
    }
    return sum;
}
void Hashinitiate(Hash* head) {//表头初始化
    for (int i = 0; i < Maxsize; i++) {
        head->arr[i].next = NULL;//将表头的NEXT域设为空
    }
}
bool HashInsert(Hash* head, char srt[]) {//将数据进行插入
    Node* p = (struct Node*)malloc(sizeof(Node));//申请节点
    p->data= srt[Max];//将字符存储到链表中
    int s = ZifuAscall(srt);//将字符串的和赋值给s;
    int index= s % 10;//取模
    p->next = head->arr[index].next;//使用头插法进行插入
    head->arr[index].next = p;
    return true;
}
void HashSearch(Hash* head, char srt[]) {//进行查找
    int index;
    int s = ZifuAscall(srt);
    index = s % Maxsize;
    Node* p = head->arr[index].next;
    for (p; p != NULL; p = p->next) {
        if (strcmp(p->data,srt[Max])==0) {
            printf("查找成功，数据为：%s\n", p->data);
        }
        else printf("查找失败\n");
    }
}
int main() {
    char ax[10][Max] = { "zhang","qweqwe","adqwqe","qweqeq","qweqw","zhag","qwqwe","adqwe","qwqeq","qweq" };
    Hash head;
    Hashinitiate(&head);
    for (int i = 0; i < Maxsize; i++) {
        HashInsert(&head, ax[i]);
    }
    printf("查找ax[10][Max] = {zhang,qweqwe,adqwqe,qweqeq,qweqw,zhag,qwqwe,adqwe,qwqeq,qweq }\n");
    for (int i = 0; i < Maxsize; i++) {
        HashSearch(&head, ax[i]);
    }    
}

想得出主函数里面的结果

Answer 1

#define ll long long   // 双Hash方法，不同的Base和MOD，相当于两次 单Hash
ll Base1 = 29;
ll Base2 = 131;
ll MOD1 = 1e9 + 7;
ll MOD2 = 1e9 + 9;
const int MAXN = 2e4 + 50;
 
class Solution {
public:
    set< pair <ll, ll> > H;  // 因为是一个二元组，所以可以用 pair 容器。
    ll h1[MAXN], h2[MAXN], p1[MAXN], p2[MAXN];
 
    int distinctEchoSubstrings(string text) {
        int n = text.size();
        h1[0] = 0, h2[0] = 0, p1[0] = 1, p2[0] = 1;
        for(int i = 0;i < n;i++)
        {
            h1[i+1] = (h1[i]*Base1 + (text[i] - 'a' + 1)) % MOD1;
            h2[i+1] = (h2[i]*Base2 + (text[i] - 'a' + 1)) % MOD2;
        }
            
        
        for(int i = 1;i < n;i++)
        {
            p1[i] = (p1[i-1]*Base1) % MOD1;
            p2[i] = (p2[i-1]*Base2) % MOD2;
        }
           
 
        for(int len = 2; len <= n; len += 2)
        {
            for(int i = 0;i + len -1 < n;i++)
            {
                int x1 = i, y1 = i + len/2 - 1;
                int x2 = i + len/2, y2 = i + len - 1;
                ll left1 = ((h1[y1 + 1] - h1[x1] * p1[y1 + 1 - x1]) % MOD1 + MOD1) % MOD1;
                ll right1 = ((h1[y2 + 1] - h1[x2] * p1[y2 + 1 - x2]) % MOD1 + MOD1) % MOD1;
                ll left2 = ((h2[y1 + 1] - h2[x1] * p2[y1 + 1 - x1]) % MOD2 + MOD2) % MOD2;
                ll right2 = ((h2[y2 + 1] - h2[x2] * p2[y2 + 1 - x2]) % MOD2 + MOD2) % MOD2;
 
                if(left1 == right1 && left2 == right2) H.insert(make_pair(left1, left2));
            }
        }
        return H.size();
    }
};