Cod sursa(job #2288725)

Utilizator DeleDelegeanu Alexandru Dele Data 23 noiembrie 2018 19:50:57
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#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;
}