Cod sursa(job #108099)

Utilizator wefgefAndrei Grigorean wefgef Data 21 noiembrie 2007 17:04:06
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int Lmax = 10000005;
const int Dmax = 32;
const int Wmax = 50005;

char s[Lmax];
char word[Dmax];
int N, M;
int Nr_cuv;
unsigned int v[Wmax];
int stp;

int search(unsigned int cuv) {
	int step = stp, p = 1;
	for (; step; step >>= 1)
		if (p+step <= Nr_cuv && v[p+step] <= cuv) p += step;
	return v[p] == cuv;
}

int main() {
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);

	fgets(s, Lmax, stdin);
	N = strlen(s)-1;

	while (fgets(word, Dmax, stdin)) {
		M = strlen(word)-1;

		unsigned int code = 0;
		for (int i = 0; i < M; ++i)
			code = code*3 + word[i]-'a';

		v[++Nr_cuv] = code;
	}
	sort(v+1, v+Nr_cuv+1);

	stp = 1;
	while (2*stp < Nr_cuv) stp <<= 1;

	unsigned int code = 0;
	unsigned int pow = 1;

	for (int i = 1; i < M; ++i)
		pow *= 3;

	int ret = 0;

	for (int i = 0; i < M; ++i)
		code = code*3 + s[i]-'a';
	ret += search(code);

	for (int i = M; i < N; ++i) {
		code -= pow * (s[i-M]-'a');
		code = code*3 + s[i]-'a';

		ret += search(code);
	}
	printf("%d\n", ret);
}