-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.cpp
More file actions
214 lines (167 loc) · 6.13 KB
/
Copy pathmain.cpp
File metadata and controls
214 lines (167 loc) · 6.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
// Created by Vecnik88
/*
Хеширование цепочками
Хеширование цепочками — один из наиболее популярных методов реализации
хеш-таблиц на практике. Ваша цель в данной задаче — реализовать такую схему,
используя таблицу с m ячейками и полиномиальной хеш-функцией на строках.
Ваша программа должна поддерживать следующие типы запросов:
• add string: добавить строку string в таблицу. Если такая
строка уже есть, проигнорировать запрос;
• del string: удалить строку string из таблицы. Если такой
строки нет, проигнорировать запрос;
• find string: вывести «yes» или «no» в зависимости от того,
есть в таблице строка string или нет;
• check i: вывести i-й список (используя пробел в качестве раз-
делителя); если i-й список пуст, вывести пустую строку.
При добавлении строки в цепочку, строка должна добавляться в начало цепочки.
Формат входа. Первая строка размер хеш-таблицы m. Следующая
строка содержит количество запросов n. Каждая из последую-
щих n строк содержит запрос одного из перечисленных выше
четырёх типов.
Формат выхода. Для каждого из запросов типа find и check выве-
дите результат в отдельной строке.
Ограничения. 1 ≤ n ≤ 105; 5 ≤ m ≤ n. Все строки имеют длину
от одного до пятнадцати и содержат только буквы латинского
алфавита.
Пример.
Вход:
5
12
add world
add HellO
check 4
find World
find world
del world
check 4
del HellO
add luck
add GooD
check 2
del good
Выход:
HellO world
no
yes
HellO
GooD luck
*/
#include <cmath>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <forward_list>
using namespace std;
uint64_t hashFunction(const string& str, const unsigned &m); // <---. хэш-функция
void check_str(vector<forward_list<string>>&, const string&); // <---. проверяет i-тый список таблицы
void del_str(vector<forward_list<string>>&, const string&, const unsigned&); // <---. удаляет строку
void add_str(vector<forward_list<string>>&, const string&, const unsigned&); // <---. добавляет строку
void find_str(vector<forward_list<string>>&, const string&, const unsigned&); // <---. поиск строки
int main()
{
uint32_t n = 0; // <---. количество запросов
uint32_t sizeHashTable = 0; // <---. размер хэш-таблицы
string str = ""; // <---. рабочая строка
cin >> sizeHashTable >> n;
cin.ignore();
vector<forward_list<string>>table(sizeHashTable);
while(n > 0)
{
getline(cin, str);
switch(str[0])
{
case 'a':
add_str(table, str, sizeHashTable);
break;
case 'f':
find_str(table, str, sizeHashTable);
break;
case 'c':
check_str(table, str);
break;
case 'd':
del_str(table, str, sizeHashTable);
break;
}
--n;
}
return 0;
}
void find_str(vector<forward_list<string>>&table, const string& str, const unsigned& sizeHashTable)
{
uint64_t number = 0;
uint32_t i = 5;
string str_work = "";
while(i < str.length())
str_work += str[i++];
number = hashFunction(str_work, sizeHashTable);
for(auto iter = table[number].begin(); iter != table[number].end(); ++iter)
{
if(str_work == *iter)
{
cout << "yes" << endl;
return;
}
}
cout << "no" << endl;
}
void add_str(vector<forward_list<string>>&table, const string& str, const unsigned& sizeHashTable)
{
uint64_t number = 0;
uint32_t i = 4;
string str_work = "";
while(i < str.length())
str_work += str[i++];
number = hashFunction(str_work, sizeHashTable);
for(auto iter = table[number].begin(); iter != table[number].end(); ++iter)
{
if(str_work == *iter)
return;
}
table[number].push_front(str_work);
}
void check_str(vector<forward_list<string>>&table, const string& str)
{
string str_work = "";
uint32_t i = 6;
uint64_t number = 0;
while(i < str.length())
str_work += str[i++];
istringstream is(str_work);
is >> number;
if(table[number].empty())
cout << "\n";
else
{
for(auto iter = table[number].begin(); iter != table[number].end(); ++iter)
cout << *iter << " ";
cout << endl;
}
}
void del_str(vector<forward_list<string>>&table, const string& str, const unsigned& sizeHashTable)
{
uint64_t number = 0;
uint32_t i = 4;
string str_work = "";
while(i < str.length())
str_work += str[i++];
number = hashFunction(str_work, sizeHashTable);
table[number].remove(str_work);
}
uint64_t hashFunction(const string& str, const unsigned &sizeHashTable)
{
const uint64_t mod_index = 1000000007;
const uint64_t pow_index = 263;
uint64_t result = 0;
uint64_t pow = 1;
for (size_t i = 0; i < str.length(); ++i)
{
uint64_t result_v1 = (uint64_t(str[i]) * pow) % mod_index;
result = (result + result_v1) % mod_index;
pow = (pow * pow_index) % mod_index;
}
result %= mod_index;
result %= sizeHashTable;
return result;
}