Rabbin Karrp iplementation using hash problem

[pajaPatak]

I have written hash.h file, that I want to use for implementation of RK algorithm. So far I have wrote this.

#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

and for RK algorithm

#include <bits/stdc++.h>
#include <unordered_map>
#include "hash.h"
using namespace std;

const int P_B= 227;
const int P_M = 1000005;


int rabin_karp(const string& n, const string& trazim) {

   int h1 = Hash(n);
   int h2 = 0;
   int stepen = 1;
   for (int i = 0; i < n.size(); i++)
      stepen = (stepen * P_B) % P_M;
   for (int i = 0; i < trazim.size(); i++) {
      h2 = h2*P_B + trazim[i];
      h2 %= P_M;
      if (i >= n.size()) {
         h2 -= stepen * trazim[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;
}

Now I have problem in putting this two together, in way I did the hash implementation

[jonnin]

which piece of data do you want in your hash table?
I don't know the RK algorithm you show but it should just be to figure out what piece(s) of data you want stored and fetched and putting those in your object.

[pajaPatak]

RK algorithm is the following one:

function RabinKarp(string s[1..n], string pattern[1..m])
hpattern := hash(pattern[1..m]);
for i from 1 to n-m+1
hs := hash(s[i..i+m-1])
if hs = hpattern
if s[i..i+m-1] = pattern[1..m]
return i
return not found

I need to find is there a String P ( pattern ) in string T (text). So I need to search for P in T. All that I want to do by using that hash.h.

[jonnin]

your class is a hash-table, a container.
that algorithm sure looks to me like a hash value-generator, like SHA*, (not a container).
Can you review these 2 ideas and tell me if that is the problem?
you don't need a heavy hash function if its for values. you can do a quick crc type; it looks like you need what is called a rolling-hash (I gave in and looked it up) which can be done with crcs.

A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input.
https://en.wikipedia.org/wiki/Rolling_hash

a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern
https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

[pajaPatak]

I have done this problem using rolling hash function and that all works just fine, but now I also have to do it with this exact hash function I have written in hash.h. At the end I came to this point where I do not know what to do next, how to make it working and how to put it all together.

[jonnin]

you need to take the hash function and isolate it to just return the index/ result number then, and call that without using the container parts of the class, or just make a stand-alone function out of the class that runs that small piece of it.

[pajaPatak]

What do you mean by isolating just to return index? Do I need to make function that just returns keys or number of elements? What I am going to do with rest of class, can I dismiss it ? Is that (the only ) function I need to call later in code for (RK) algorithm (instead
int h1 = Hash(n);] I call that new function that is in header )?

[jonnin]

Hash(n) ... I don't see this, but the mismatched {}s and indentation in the forum is not helping me spot it.
If that returns what you want, then use it exactly the same way you used it in the one that worked with your rolling hash function.

[pajaPatak]

Thanks a lot!!!

Btw it is on line 12th in (RK) implementation (in post 2nd code).

[jonnin]

yes, I see that one. but where do you define int Hash(string)?