Cod sursa(job #102423)

Utilizator wefgefAndrei Grigorean wefgef Data 14 noiembrie 2007 13:16:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.02 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 search(int st, int dr, unsigned int cuv) {
	int m;
	while (st != dr) {
		m = (st+dr+1)/2;
		if (v[m] <= cuv) st = m;
		else dr = m-1;
	}
	return v[st] == 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);

	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(1, Nr_cuv, code);

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

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