Как сравнить 2 строки по хешам - PullRequest
Новая
       18

Как сравнить 2 строки по хешам

0 голосов
/ 03 ноября 2018

Если у меня есть 2 строки (1 игла и 1 стог сена), и я хочу сравнить все подстроки (одинаковой длины иглы) хэша в стоге сена с хэшем строки иглы.

пример: 

na      << needle   , pHashes: 0 14 45 0 0 0 0 0 0  , needle hash = 45
banana  << haystack , pHashes: 0 2 33 13487 43278 12972572 41601723 0 0 
-----------------------------
^^      << 1st substring (ba)
 ^^     << 2nd substring (an)
  ^^    << 3rd substring (na)
   ^^   << 4th substring (an)
    ^^  << 5th substring (na)

Я хочу вычислить все префиксы хэшей строки стога сена и вычислить значение хеша индексов i и j, чтобы получить хеш подстроки s [i… j]. ех. проверить, если хеш (игла) == хеш (3-я подстрока)

я использую функцию getHash, чтобы получить хеш строки: 

const long long hashMod = (long long) ( 1e15 + 9 );
const int prime = 31;

long long getHash(string str) {
    const int len = str.length();
    ll hash = 0, powVal = 1;
    for (int i = 0; i < len; ++i) {
        hash = ( hash + ( str[i] - 'a' + 1 ) * powVal ) % hashMod;
        ( powVal *= prime ) %= hashMod;
    }
    return hash;
}

и функция get(l , r) для получения хеша диапазона [l ... r]: 

long long get(int l, int r) {
    const int len = haystack.length();
    return ( ( pHashes[r] - pHashes[l-1] ) * powers[len - r]) % hashMod;
}

powers[] = 1 31 961 29791 923521 28629151

моя главная проблема с перемещением всех подстрок в одну и ту же степень.

...