Реализация алгоритма Рабина-Карпа на C++

Программирование Программирование на С++ Решение задач на С++ Реализация алгоритма Рабина-Карпа на C++

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 6 мес. назад.

  • Автор
    Сообщения
  • #5566
    @admin

    Алгоритма Рабина-Карпа реализует поиск подстроки в строке. Алгоритм представляет из себя улучшенную версию последовательного поиска, улучшение заключается в использовании хэш-функции. Это объясняется тем, что сравнить два числа(два хэша) гораздо быстрее и дешевле, чем сравнивать подстроки посимвольно. Сравнивать подстроки придется только один раз, когда хэши совпали, сделать это придется для увеличения надежности и защиты от случая коллизии хэша.

    Для алгоритма Рабина-Карпа принято использовать так называемый кольцевой хэш. Его преимущество в том, что хэш следующей подстроки в тексте будет напрямую зависеть от хэша предыдущей. Поэтому мы сможем очень дешево двигаться по тексту и пересчитывать хэши.

    Формула хэша подстроки:
    $$H = C_1 \cdot h^{k-1} + C_2 \cdot h^{k-2} + C_k \cdot h^{0}$$
    Тут Ci — входные символы, h константа. Удаление символов из подстроки и добавление новых производится путем вычитания последнего члена формулы и добавлением первого соответственно.

    Конечно, можно использовать любой другой хэш, не обязательно кольцевой.

    Реализация кольцевой хэш-функции на C++

    Функция на вход принимает строку для подсчета хэша, ее длину, предыдущий хэш, указатель на константу h. Указатель потому, что она должны быть общей для многих вызовов функции, я решил не делать ее глобальной, а просто завести выше по стеку и работать с ней по указателю.

    В начале проверяем, если константа не инициализирована, то высчитываем ее функцией hInit(). Далее идет проверка, что это первый хэш, тогда просто высчитываем его по формуле, иначе, согласно правилу пересчета, вычитаем первый элемент строки и добавляем последний. Возвращается новый хэш от строки.

    int hInit(unsigned int strLen) {
      int d = 52;
      int  p = 65713;
     
      int h = 1;
      for(unsigned int i=1; i < strLen; i++) {
        h = (h*d) % p;
      }
     
      return h;
    }
     
    int ringHash(char* str, unsigned int strLen, int prevHash, int *h) {
      int d = 52; //Константа из формулы
      int  p = 65713; //Вычисления производятся по модулю простого числа
     
      //h = d^(len-1) (mod p) - константа для быстроого пересчета хэша
      if(*h == 0) { //Если константа не инициализирована
        *h = hInit(strLen);
      }
     
      //Если считаем хеш первый раз
      if(prevHash == 0) {
        for(unsigned int i=0; i<strLen; i++) {
          prevHash += (d*prevHash + (int)str[i]) % p;
        }
        if(prevHash < 0) {
          prevHash += p;
        }
     
        return prevHash;
      }
      //Если пересчитываем для другого окна
      else {
        int hash = (d * (prevHash - (int)str[0] * (*h)) + (int)str[strLen]) % p;
        if(hash < 0) {
          hash += p;
        }
     
        return hash;
      }
    }

    Реализация алгоритма Рабина-Карпа на C++

    На вход принимает текст и строку, которую нужно найти в тексте. Кроме всего прочего, здесь я объявляю константу для быстрого пересчета хэша и отдаю указатель на нее в кольцевую функцию. Бежим по тексту, высчитываем хэш очередного «окна», сравниваем его с хэшом строки, если совпали, пробегаемся посимвольно и отдаем индекс вхождения подстроки.

    int rabinKarpSearch(char* text, char* str) {
      unsigned int strLen = strlen(str);
      unsigned int textLen = strlen(text);
      int h = 0;
     
      //Хэш подстроки для поиска
      int strHash = ringHash(str, strLen, 0, &h);
      //Хэш первого окна в тексте
      int textHash = ringHash(text, strLen, 0, &h);
     
      for(unsigned int k = 0; k <= (textLen-strLen); k++) {
        if(strHash == textHash) {
          //Если хэши совпали, проверяем посимвольно
          for(unsigned int i = 0; (i < strLen) && (str[i] == text[k+i]); i++) {
            if(i == (strLen-1)) {
              return k;
            }
          }
        }
        //Хэш следующего окна
        textHash = ringHash(&text[k], strLen, textHash, &h);
      }
      //Строка не найдена
      return -1;
    }

    Материал взят тут: http://mindhalls.ru/rabin-karp-search/

Для ответа в этой теме необходимо авторизоваться.