@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 << " "; 
  }
}
  • Вопрос задан
  • 170 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Ну хоть бы написали, что за хеши вы тут считаете. Похоже у вас полиномиальных хеш.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы