Cod sursa(job #100321)

Utilizator eferLiviu Ciortea efer Data 12 noiembrie 2007 02:25:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 3.57 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <iostream>
#include <ctime>
using namespace std;

#define REP(i, N) for (i = 0; i < (N); ++i)
#define REPV(i, a, b) for (i = (a); i <= (b); ++i)
#define REPD(i, N) for (i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (i = (b); i >= (a); --i)
#define REPIT(it, a) for (it = (a).begin(); it != (a).end(); ++it)
#define CLR(a) memset(a, 0, sizeof(a))
#define MSET(a, v) memset(a, v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(source))
#define PB push_back
#define SZ(a) (int)(a).size()
#define ALL(a) ((a).begin(), (a).end())
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<string> VS;

const int MAXH = 1<<20;
const int MAXN = 51200;
const int MAXHM = MAXH - 1;
const int MAXL = 32;
int N, M, size[MAXH];
char buff[MAXL];
//LL * hash[MAXH];
int first[MAXH], next[MAXN], C;
LL val[MAXN];

const int MAXS = 10000020;
char str[MAXS];

int hashcode(LL num) {
	//unsigned int h = 0;
	//int i;


	//REP(i, M) {
	//	h = ((h << 5) + h) + (num & 3);
	//	num >>= 2;
	//}

	return num & MAXHM;
	//return h % MAXH;
	//return num % MAXH;
}

int find(LL num) {
	int ind = hashcode(num), r = first[ind];
	//vector<LL>& h = hash[ind];
	//REP(i, SZ(h)) if (h[i] == num) return 1;
	//REP(i, size[ind]) if (hash[ind][i] == num) return 1;
	while (r != -1) {
		if (val[r] == num) return 1;
		r = next[r];
	}
	return 0;
}

void puthash(LL num) {
	int ind = hashcode(num);
	if (!find(num)) {
		//if (!size[ind]) hash[ind] = new LL[MAXSLOTS];
		//assert(size[ind]+1 < MAXSLOTS);
		//hash[ind][size[ind]++] = num;
		//hash[ind].PB(num);
		next[C] = first[ind];
		first[ind] = C;
		val[C] = num;
		C++;
	}
}

LL encode() {
	M = strlen(buff) - 1;
	LL res = 0;
	int i;
	//REP(i, M) res = (res << 2) | (buff[i] - 'a');
	REP(i, M) res += (res<<1) + buff[i] - 'a';

	return res;
}

//int putend() {
//	int p = 0, start = max(M-10, 0), i;
//	REPV(i, start, M-1) p += (p<<1) + buff[i] - 'a';
//	have[p] = true;
//	return p;
//}

void parsewords() {
	//scanf("%s", str);
	fgets(str, MAXS, stdin);
	for (;;) {
		if (!fgets(buff, MAXL, stdin)) break;
		puthash(encode());
		//putend();
		N++;
	}
}

int main() {
	//time_t start = clock();
	freopen("abc2.in", "rt", stdin);
	freopen("abc2.out", "wt", stdout);

	MSET(first, -1);
	MSET(next, -1);

	//random_shuffle(primes, primes + (sizeof(primes) / sizeof(primes[0])));

	parsewords();

	//fprintf(stderr, "%lf\n", 1.0 * (clock() - start) / CLK_TCK);

	int S = strlen(str) - 1;
	if (S < M) {
		printf("0\n");
		return 0;
	}

	int i;
	//REP(i, MAXH) if (size[i] > 4) fprintf(stderr, "%d ", size[i]);

	//LL mask = 0;
	//REP(i, M) mask = (mask << 2) | 3;

	strncpy(buff, str, M);
	LL curr = encode();
	//int end = putend();

	LL pw = 1;
	REP(i, M-1) pw *= 3;
	//int endpw = 1, h = min(M, 10);
	//REP(i, h-1) endpw *= 3;

	int res = find(curr);

	REPV(i, M, S-1) {
		//curr = (curr << 2) | (str[i] - 'a');
		//curr &= mask;
		if (str[i-M] == 'b') curr -= pw;
		else if (str[i-M] == 'c') curr -= pw<<1;
		curr += (curr<<1) + str[i] - 'a';

		//if (str[i-h] == 'b') end -= endpw;
		//else if (str[i-h] == 'c') end -= endpw<<1;
		//end += (end<<1) + str[i] - 'a';

		//if (have[end]) res += find(curr);
		if (find(curr)) res++;
	}

	printf("%d\n", res);

	//fprintf(stderr, "%lf\n", 1.0 * (clock() - start) / CLK_TCK);

	return 0;
}