Конечно, мне нужно реализовать алгоритм поиска строк Рабина-Карпа с другой реализацией ha sh. Сначала я сделал ха-1009 *, и это прекрасно работает. Проблема в том, что когда речь идет о линейном и раздельном сцеплении, ха sh. Я сделал линейный заголовочный файл ha sh и для основных методов ha sh он работает. Хорошо, также я написал алгоритм Рабина-Карпа, который работает с другими версиями ha sh. Но сейчас я не знаю, как соединить эти два.
Вот что я написал к настоящему моменту, ха sh .h
#ifndef HASH_H
#define HASH_H
#include <vector>
using namespace std;
template <typename Tip>
class Hash {
struct Element {
int key;
Tip value;
int mark; //0 free, 1 occupied, 2 was occupied
Element(int key = 0, Tip value = Tip(), int mark = 1):key(key),value(value),mark(mark){}
};
int h1(int key) {
return key%capacity;
}
int h2(int key) {
return 2*(key%5) + 1;
}
int capacity;
int no_of_elements;
const double factor_of_full;
vector<Element> Tabel;
public:
Hash():capacity(128),no_of_elements(0),factor_of_full(0.5){
Tabel.resize(capacity);
for(int i=0;i<capacity;i++)
Tabel[i].mark = 0;
}
void Insert(pair<int,Tip> element);
Tip Find(int key);
void Delete(int key);
};
template <typename Tip>
void Hash<Tip>::Insert(pair<int,Tip> element) {
if((double(no_of_elements+1))/capacity>factor_of_full) {
vector<Element> coppy = Tabel;
capacity*=2;
Tabel.resize(capacity);
no_of_elements = 0;
for(int i=0;i<Tabel.size();i++)
Tabel[i].mark = 0;
for(int i=0;i<coppy.size();i++)
if(coppy[i].mark == 1)
Insert({coppy[i].key,coppy[i].value});
}
int index = h1(element.first);
while(Tabel[index].mark == 1)
index = (index + h2(element.first))%capacity;
Tabel[index] = Element(element.first,element.second);
no_of_elements++;
}
template <typename Tip>
Tip Hash<Tip>::Find(int key) {
int index = h1(key);
for(int i=0;i<capacity;i++) {
if(Tabel[index].mark == 0)
break;
if(Tabel[index].mark == 1 && Tabel[index].key == key)
return Tabel[index].value;
else index = (index+h2(key))%capacity;
}
return Tip();
}
template <typename Tip>
void Hash<Tip>::Delete(int key) {
int index = h1(key);
for(int i=0;i<capacity;i++) {
if(Tabel[index].mark == 0)
return;
if(Tabel[index].mark == 1 && Tabel[index].key == key) {
Tabel[index].mark = 2;
no_of_elements--;
}
else index = (index+h2(key))%capacity;
}
return;
}
#endif // HASH_H
Rabin_Karp. cpp
#include <bits/stdc++.h>
#include "hash.h"
using namespace std;
const int P_B= 227;
const int P_M = 1000005;
int rabin_karp(const string& n, const string& find) {
int h1 = Hash(n);
int h2 = 0;
int pow = 1;
for (int i = 0; i < n.size(); i++)
pow = (pow * P_B) % P_M;
for (int i = 0; i < find.size(); i++) {
h2 = h2*P_B + find[i];
h2 %= P_M;
if (i >= n.size()) {
h2 -= pow * find[i-n.size()] % P_M;
if (h2 < 0)
h2 += P_M;
}
if (i >= n.size()-1 && h1 == h2)
return i - (n.size()-1);
}
return -1;
}