#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]);
}
}
想得出主函数里面的结果
#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();
}
};