Cod sursa(job #240951)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 8 ianuarie 2009 22:34:18
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define LMAX 10000010
#define DMAX 64
#define MAXN 50010

using namespace std;

long i, n, m, cuv, stp, num, p, sol;
char s[LMAX], word[DMAX];
long v[MAXN];

long search(long cuv);
void read_data();

int main() {
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	read_data();
	sort(v + 1, v + cuv + 1);
	stp = 1;
	while (2 * stp < cuv) {
		stp <<= 1;
	}
	num = 0;
	p = 1;
	for (i = 1; i < m; ++i) {
		p *= 3;
	}
	for (i = 0; i < m; ++i) {
		num = num * 3 + s[i] - 'a';
	}
	sol += search(num);
	for (i = m; i < n; ++i) {
		num -= p * (s[i - m] - 'a');
		num = num * 3 + s[i] - 'a';
		sol += search(num);
	}
	printf("%ld\n", sol);
	return 0;
}

long search(long cuv) {
	long step = stp, p = 1;
	for (; step; step >>= 1) {
		if (p + step <= cuv && v[p + step] <= cuv) {
			p += step;
		}
	}
	if (v[p] == cuv) {
		return 1;
	} else {
		return 0;
	}
}

void read_data() {
	fgets(s, LMAX, stdin);
	n = strlen(s) - 1;
	while (fgets(word, DMAX, stdin)) {
		m = strlen(word) - 1;
		long num = 0;
		for (i = 0; i < m; ++i) {
			num = num * 3 + word[i] - 'a';
		}
		v[++cuv] = num;
	}
}