Почему не работают хеши?

Question

[fronttrty]

написал хэш функцию но gethash выдаёт не правильное значение вот код

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

#define ll long long

ll p = 400;
ll M = 1000000007; 

void powof(ll x, vector<ll>&powx){
  powx[0] = 1;
  ll z = x;
  for(int i = 1; i < powx.size(); i++){
    powx[i] = x;
    x = x * z % M;
  }
}

ll gethash(ll l, ll r, vector<ll> prefhash, vector<ll> powp){
  if(l == 0) return prefhash[r];
  return abs(prefhash[r] - prefhash[l-1] * powp[r - l + 1]% M + M) % M;
}

ll xhash(string s, ll l, ll r){
  ll hash = long (s[l]); 
  if(l == r) return long (s[l]); 
  for(int i = l; i < r + 1; i++){
    hash = (hash * p + int(s[i])) % M;
  }
  return hash;
}

int main() {
  string s1,s2;
  ll hs2;
  cin >> s1 >> s2;
  vector<ll> hs1(s1.size());
  vector<ll> powp(s1.size() + 1);
  for(int i = 0; i < s1.size(); i++){
    hs1[i] = xhash(s1,0,i);
  }
  hs2 = xhash(s2,0,s2.size()-1);
  powof(p,powp);
  for(auto u : hs1){
    cout << u << " " ; 
  }
  cout << endl;
  for(auto u : powp){
    cout << u << " "; 
  }
}

Comments

[15432]

Как вы определяете правильность результата?

[fronttrty]

15432 сравниваю gethash для подстроки s1 и xhash для s2 совпадающей с подстрокой

Answer 1

[Wataru]

Ну хоть бы написали, что за хеши вы тут считаете. Похоже у вас полиномиальных хеш.

И xhash и gethash написаны с ошибками.

Давайте посмотрим на xhash. Если l==r, то вернется s[l]*1. Вроде правильно. Если l+1=r, то ваша функция вернет s[l]*p^2+s[l]*p+s[r]. Вряд ли это то, чего вы хотели добиться. Или инициализация перед циклом неверная, или границы у цикла.

Comments

[fronttrty]

Илья Николаевский
спасибо, исправил. А что не так c gethash

[fronttrty]

ll gethash(ll l, ll r, vector<ll> prefhash, vector<ll> powp){
  if(l == 0) return prefhash[r];
  return abs(prefhash[r] - prefhash[l-1] * powp[r - l + 1]) % M;
}

[Wataru]

fronttrty, Зачем там abs?

[fronttrty]

Илья Николаевский чтобы не было отрицательных значений

[Wataru]

fronttrty, Давайте сначала. Запишите формулу хеша на отрезке l..r. Запишите формулу для каждого prefhash и powp. Запишите как ваш getshash считает, приравняйте, посмотрите, то ли у вас получилось.

[jcmvbkbc]

чтобы не было отрицательных значений

fronttrty, можно было использовать unsigned long long и считать беззнаковой арифметикой.

[fronttrty]

Илья Николаевский да всё получилось модуль не нужен

[fronttrty]

но тогда для деления с остатком нужно написать свою функцию

[Wataru]

jcmvbkbc, Если пользоваться беззнаковой арифметикой, то как считать (a-b) % m?

Если же сделать номальную формулу, то она будет работать и при знаковых числах: (a+m-b%m)%m.

[jcmvbkbc]

Если пользоваться беззнаковой арифметикой, то как считать (a-b) % m?

Илья Николаевский, если я правильно понял, у ТС нет определённого плана, какой должна быть хеш-функция, но отрицательные результаты где-то ему испортили жизнь. Если так, то не важно, что там будет внутри.

[Wataru]

jcmvbkbc, Проблема ТС в том, что x%m при отрицательном m выдаст неверное, отрицательное число. Да, с тем же остатком, но в вычислениях нужно число от 0 до m-1. Правильное решение этой проблемы - прибавить m, если число отрицательно, или всегда прибавлять m и брать по модулю опять. ТС же, наобум вставил модуль. Если же тупо заменить все переменные на unsigned int, то там будет переполнение и, фактически, прибавление 2^32 к ответу. Что тоже испортит ответ, если только m - не степень двойки.

[jcmvbkbc]

Правильное решение этой проблемы

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

Если же тупо заменить все переменные на unsigned int, то там будет переполнение

у беззнаковой арифметики нет переполнения.

[Wataru]

jcmvbkbc, Ну по коду очевидно же, что тут попытка написать полиномиальный хеш.

> у беззнаковой арифметики нет переполнения.

И чему будет равно 1 - 2 в unsigned int?

[jcmvbkbc]

> у беззнаковой арифметики нет переполнения.
И чему будет равно 1 - 2 в unsigned int?

Илья Николаевский, я вам привёл ссылку на стандарт с буквально этой фразой. Хотите поспорить со стандартом -- можете делать это на прямую, без моего участия.

[Wataru]

jcmvbkbc, Просто повторение фраз из стандарта, без какой-либо попытки их осмыслить, обычно плохо кончаются (второй пример там).

Стандарт лишь говорит, что нет никакого UB, и вычисления производятся по модулю 2^n. В русском языке термина для "underflow" особо нет, поэтому я использовал слово "переполнение".

Если проблема "чтобы не было отрицательных значений" - то предлагать unsigned - это весьма необдуманное решение.

[jcmvbkbc]

В русском языке термина для "underflow" особо нет

Илья Николаевский, там где переполнение возможно, стандарт не делает разницы между overflow и underflow. То что происходит при вычислении 1 - 2 в unsigned int -- это не underflow. Это арифметика по модулю. Стандарт говорит, что нет никакого -flow в беззнаковых вычислениях. overflow и underflow -- свойства исключительно знаковых операций.

[Wataru]

jcmvbkbc, Хорошо, был не прав. Мой комментарий должен был быть:

Если же тупо заменить все переменные на unsigned int - то там будет вычисление по не тому модулю (2^32)