Pagini recente » Cod sursa (job #2370154) | Cod sursa (job #2387080) | Cod sursa (job #563241) | Cod sursa (job #1056269) | Cod sursa (job #2288725)
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <cstring>
#define MAXT 10000001
#define MAXW 21
#define myModulo
std::ifstream f("abc2.in");
std::ofstream g("abc2.out");
char myText[MAXT];
char word[MAXW];
char myWord[MAXW];
class HashMap {
private:
struct HashNode {
char value[MAXW];
HashNode*next;
};
HashNode **table;
int capacity;
public:
HashMap(int capacity) {
this->capacity = capacity;
table = new HashNode*[capacity];
for (int i = 0; i < capacity; ++i)
table[i] = NULL;
}
int getHashKey(char value[MAXW]) {
int key = value[0];
int lg = strlen(value);
for (int i = 1; i < lg; ++i) {
key = (key * 256 + value[i]) % capacity;
}
return key;
}
void insert(int key, char value[MAXW]) {
HashNode*t = new HashNode;
strcpy(t->value, value);
t->next = NULL;
if (table[key] == NULL) {
table[key] = t;
return;
}
HashNode*q;
for (q = table[key]; q->next; q = q->next)
if (strcmp(t->value, q->value) == 0)
return;
if (strcmp(t->value, q->value) == 0)
return;
q->next = t;
}
bool search(int key, char value[MAXW]) {
for (HashNode*q = table[key]; q; q = q->next)
if (strcmp(q->value, value) == 0)
return true;
return false;
}
void remove(int key, char value[MAXW]) {
if (table[key] == NULL)
return;
if (strcmp(table[key]->value, value) == 0) {
HashNode*temp = table[key];
table[key] = table[key]->next;
delete temp;
return;
}
for (HashNode*q = table[key]; q->next; q = q->next)
if (strcmp(q->next->value, value) == 0) {
HashNode*temp = table[key]->next;
q->next = q->next->next;
delete temp;
return;
}
}
void displayTable() {
std::cout << "\n[Hash Table]\n";
for(int i=0 ; i<capacity ; ++i)
if (table[i] != NULL) {
std::cout << "Key: " << i << " <-> nodes: ";
for (HashNode*q = table[i]; q; q = q->next)
std::cout << q->value;
std::cout << '\n';
}
std::cout << "\n\n";
}
};
int main() {
f >> myText;
int tLg = strlen(myText);
f >> word;
int wLg = strlen(word);
HashMap* h = new HashMap(300007);
tLg -= 3;
for (int i = 0; i < tLg; ++i) {
strncpy(myWord, myText + i, wLg);
int key = h->getHashKey(myWord);
h->insert(key, myWord);
}
int nr;
int key = h->getHashKey(word);
if (h->search(key, word)) {
nr = 1;
h->remove(key, word);
}
else
nr = 0;
while (f >> word) {
int key = h->getHashKey(word);
if (h->search(key, word)) {
++nr;
h->remove(key, word);
}
}
g << nr << '\n';
return 0;
}