Рабин Карп с использованием линейного хэша - PullRequest
0 голосов
/ 14 февраля 2020

Конечно, мне нужно реализовать алгоритм поиска строк Рабина-Карпа с другой реализацией 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;
}
...