Файл: Применение алгоритмов поиска в массивах.pdf

    system("pause");

  return 0;

}

Приложение В

Поиск на основе Хеша. Листинг.

#include <bits/stdc++.h>

using namespace std;

const int SIZE = 100100;

const int BASE = 2017;

const int MOD = 1000000009;

int64_t hash[SIZE];

void init_hash(const string &line, int64_t *h, int base, int mod)

{

h[0] = 0;

int n = line.length();

for (int i = 1; i <= n; ++i)

{

h[i] = h[i - 1] * base % mod + (signed char)line[i - 1] % mod;

}

}

int64_t powers[SIZE];

void init_powers(int64_t *p, int base, int mod)

{

p[0] = 1;

for (int i = 1; i < SIZE; ++i)

{

p[i] = p[i - 1] * base % mod;

}

}

int64_t get_hash(int l, int r, int64_t *h, int64_t *p, int mod)

{

return (h[r] - h[l] * p[r - l] % mod + mod) % mod;

}

#include <bits/stdc++.h>

using namespace std;

const int SIZE = 100100;

const int BASE = 2017;

const int MOD = 1000000009;

int64_t ahash[SIZE];

int64_t bhash[SIZE];

int64_t powers[SIZE];

void init_powers(int64_t *p, int base, int mod)

{

p[0] = 1;

for (int i = 1; i < SIZE; ++i)

{

p[i] = p[i - 1] * base % mod;

}

}

void init_hash(const string &line, int64_t *h, int base, int mod)

{

h[0] = 0;

int n = line.length();

for (int i = 1; i <= n; ++i)

{

h[i] = h[i - 1] * base % mod + (signed char)line[i - 1] % mod;

}

}

int64_t get_hash(int l, int r, int64_t *h, int64_t *p, int mod)

{

return (h[r] - h[l] * p[r - l] % mod + mod) % mod;

}

int main()

{

string a, b;

cin >> a >> b;

init_powers(powers, BASE, MOD);

init_hash(a, ahash, BASE, MOD);

init_hash(b, bhash, BASE, MOD);

int q;

cin >> q;

while (q--)

{

int al, ar, bl, br;

cin >> al >> ar >> bl >> br;

--al; --bl;

if (get_hash(al, ar, ahash, powers, MOD) == get_hash(bl, br, bhash, powers, MOD))

{

cout << "YES\n";

}

else

{

cout << "NO\n";

}

}

return 0;

}

Приложение Г

Фильтр Блума. Листинг.

#include <vector>

struct BloomFilter {

BloomFilter(uint64_t size, uint8_t numHashes);

void add(const uint8_t *data, std::size_t len);

bool possiblyContains(const uint8_t *data, std::size_t len) const;

private:

uint64_t m_size;

uint8_t m_numHashes;

std::vector<bool> m_bits;

};

#include "BloomFilter.h"

#include "MurmurHash3.h"

BloomFilter::BloomFilter(uint64_t size, uint8_t numHashes)

: m_size(size),

m_numHashes(numHashes) {

m_bits.resize(size);

}

std::array<uint64_t, 2> hash(const uint8_t *data,

std::size_t len) {

std::array<uint64_t, 2> hashValue;

MurmurHash3_x64_128(data, len, 0, hashValue.data());

return hashValue;

}

inline uint64_t nthHash(uint8_t n,

uint64_t hashA,

uint64_t hashB,

uint64_t filterSize) {

return (hashA + n * hashB) % filterSize;

}

void BloomFilter::add(const uint8_t *data, std::size_t len) {

auto hashValues = hash(data, len);

for (int n = 0; n < m_numHashes; n++) {

m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)] = true;

}

}

bool BloomFilter::possiblyContains(const uint8_t *data, std::size_t len) const {

auto hashValues = hash(data, len);

for (int n = 0; n < m_numHashes; n++) {

if (!m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)]) {

return false;

}

}

return true;

}

Приложение Д

Бинарное дерево поиска. Листинг.

#include <cstdlib>

#include <cstdio>

using namespace std;

typedef struct t_node {

int key;

struct t_node* left;

struct t_node* right;

} Node, *Tree;