Поиск подстроки в другой строке с использованием хеширования - PullRequest
Новая
       5

Поиск подстроки в другой строке с использованием хеширования

0 голосов
/ 26 марта 2020

Я написал код для поиска подстроки в другой строке с использованием хэширования, но это дает мне неверный результат.

Описание работы кода:

  1. Сохранение первой n степеней p=31 в массиве pows.
  2. Сохранение хэшей для каждой подстроки s[0..i] в массиве h.
  3. Вычисление га sh для каждой подстроки длиной 9 с использованием массива h и сохраните его в наборе.
  4. Ха sh строка t и сохраните ее ха sh.
  5. Сравните ха sh из t и хэшей в наборе.

Ха sh h[n2-1] должно существовать в наборе, но его нет. Не могли бы вы помочь мне найти ошибку в коде?

Примечание: Когда я использую модульную инверсию вместо умножения на pows[i-8], код работает хорошо. 


#include <bits/stdc++.h>

#define m 1000000007
#define N (int)2e6 + 3

using namespace std;

long long pows[N], h[N], h2[N];

set<int> ss;

int main() {

    string s = "www.cplusplus.com/forum";

    // powers array
    pows[0] = 1;
    int n = s.length(), p = 31;
    for (int i = 1; i < n; i++) {
        pows[i] = pows[i - 1] * p;
        pows[i] %= m;
    }

    // hash from 0 to i array
    h[0] = s[0] - 'a' + 1;
    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + (s[i] - 'a' + 1) * pows[i];
        h[i] %= m;
    }

    // storing each hash with 9 characters in a set
    ss.insert(h[8]);
    for (int i = 9; i < n; i++) {
        int tp = h[i] - h[i - 9] * pows[i - 8];
        tp %= m;
        tp += m;
        tp %= m;
        ss.insert(tp);
    }

    // print hashes with 9 characters
    set<int>::iterator itr = ss.begin();
    while (itr != ss.end()) {
        cout << *(itr++) << " ";
    }
    cout << endl;

    // t is the string that i want to check if it is exist in s
    string t = "cplusplus";
    int n2 = t.length();
    h2[0] = t[0] - 'a' + 1;
    for (int i = 1; i < n2; i++) {
        h2[i] = h2[i - 1] + (t[i] - 'a' + 1) * pows[i];
        h2[i] %= m;
    }
    // print t hash
    cout << h2[n2 - 1] << endl;

    return 0;
}

1 Ответ

0 голосов
/ 26 марта 2020

Я вижу две проблемы с вашим кодом:

  1. Когда вы вычисляете хэши для подстрок длины 9, вы сохраняете промежуточный результат (типа long long) в int переменная. Это может привести к переполнению целого числа, и вычисленное вами значение ha sh, вероятно, будет неправильным.
  2. Для строки s = {s[0], s[1], ..., s[n-1]} способ вычисления значения ha sh: h = ∑ s[i] * p^i. В этом случае, учитывая префикс ha sh, сохраненный в h, ha sh для подстроки s[l..r] (включительно) должен составлять (h[r] - h[l - 1]) / p^(r-l+1) вместо того, что вы написали. По этой же причине использование модульного обратного (которое требуется для выполнения деления по модулю) является правильным.

Я думаю, что более распространенный способ вычисления хэшей - это наоборот, то есть h = ∑ s[i] * p^(n-i-1). Это позволяет вычислять подстроку ha sh как h[r] - h[l - 1] * p^(r-l+1), что не требует вычисления модульных инверсий.

...