Cod sursa(job #2288754)

Utilizator DeleDelegeanu Alexandru Dele Data 23 noiembrie 2018 20:28:36
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MAXT 10000001
#define MAXW 21
#define capacity 29989
#define max(a,b) ((a) > (b) ? (a) : (b))
std::ifstream f("abc2.in");
std::ofstream g("abc2.out");
char myText[MAXT];
char word[MAXW];
std::vector<unsigned int> h[capacity];
bool search(unsigned int value) {
	int key = value % capacity;
	for (auto it : h[key]) {
		if (it == value)
			return true;
	}
	return false;
}
int main() {
	f >> myText;

	int lgW = 0;
	while (f >> word) {
		lgW = max(lgW, strlen(word));
		unsigned int value = 0;
		for (int i = 0; i < lgW; ++i) {
			value = value * 3 + (word[i] - 'a');
		}
		h[value % capacity].push_back(value);
	}

	unsigned int base = 1;
	for (int i = 0; i < lgW; ++i)
		base *= 3;

	int lgT = strlen(myText);
	int lgW1 = lgW - 1;
	int nr = 0;
	unsigned int value = 0;
	for (int i = 0; i < lgT; ++i) {
		value = value * 3 + (myText[i] - 'a');

		if (i >= lgW) {
			value -= base * (myText[i - lgW] - 'a');
		}

		if (i >= lgW1) {
			nr += search(value);
		}

	}

	g << nr << '\n';

	return 0;
}