Cod sursa(job #103483)

Utilizator plastikDan George Filimon plastik Data 15 noiembrie 2007 13:23:28
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.03 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;

const int MAX_L = 10000002;
const int MAX_WL = 22;

const unsigned int  P3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401};

char T[MAX_L], w[MAX_WL];

int N, wl;
set<unsigned int> W;
vector<bool> U;

/*long long hash(const char *s) {
	int i, j;
	long long res = 0;
	for (i = 0, j = wl - 1; i < wl; ++ i, -- j)
		res = res + (s[i] - 'a') * P3[j];
	return res;
}*/

int main() {
	FILE *in = fopen("abc2.in", "r");

	//freopen("abc2.dbg", "w", stdout);

	fgets(T, MAX_L, in);

	int i, j;
	unsigned int res;
	bool no;
	char *wn;
	set<unsigned int>::iterator it;
	/*pair<multimap<long long, string>::iterator, multimap<long long, string>::iterator > pit;*/

	N = strlen(T) - 1;
	T[N] = 0;
	//puts(T);

	while (!feof(in)) {
		fgets(w, MAX_WL, in);
		wn = strchr(w, '\n');
		wl = strlen(w);
		if (wn != NULL) {
			w[wn - w] = 0;
			-- wl;
		}
		
		res = 0;
		for (i = 0, j = wl - 1; i < wl; ++ i, -- j)
			res = res + (w[i] - 'a') * P3[j];
		
		W.insert(res);
	}
	fclose(in);

	//return 0;
	/*printf("%d\n", wl);
	return 0;*/
	
	
	unsigned int hc = 0, nc = 0;
	for (i = 0, j = wl - 1; i < wl; ++ i, -- j)
		hc = hc + (T[i] - 'a') * P3[j];
	
	
	for (i = 0; i <= N - wl; ++ i) {
		//printf("%lld ", hc);

		if (W.find(hc) != W.end())
			++ nc;
		
		if (i == N - wl)
			break;
		hc -= (T[i] - 'a') * P3[wl - 1];
		hc = hc * 3 + (T[i + wl] - 'a');
		
		//printf("%lld ", hc);	
	}
	
	/*pit = W.equal_range(hc);
	for (it = pit.first; it != pit.second; ++ it)
		if (strncmp(it->second.c_str(), T + i, wl) == 0)
			++ nc;*/

	FILE *out = fopen("abc2.out", "w");
	fprintf(out, "%u\n", nc);
	fclose(out);
	/*for (it = W.begin(); it != W.end(); ++ it)
		printf("%d %s\n", it->first, (it->second).c_str());*/


	return 0;
}