Cod sursa(job #104504)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 16 noiembrie 2007 11:32:16
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.34 kb
#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

const int N_MAX = 10000010;
const int L_MAX = 22;
const int C_MAX = 50010;

char sir[N_MAX], s[N_MAX];
int cuv[C_MAX], l1, L;
int trei[L_MAX], nrcuv;

void transf(char s[], int poz)
{
	int i;

	for (i = 0; i < l1; i ++) {
		cuv[poz] += (s[i] - 'a') * trei[i];
	}
}

int find(int val)
{
	int i, step;
	for (step = 1; step < nrcuv; step <<= 1);
	for (i = 0; step; step >>= 1) {
		if (i + step <= nrcuv && cuv[i + step] <= val) i += step;
	}

	if (cuv[i] == val) return 1;
	
	return 0;
}

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

	int i;

	//puterile lui 3
	trei[0] = 1;
	for (i = 1; i <= 20; i ++) {
		trei[i] = trei[i - 1] * 3;
	}
	//end of puterile lui 3

	fgets(sir, sizeof(sir), stdin);
	L = strlen(sir) - 1;
	sir[L] = '\0';

	fgets(s, sizeof(s), stdin);
	l1 = strlen(s) - 1;

	nrcuv ++;
	transf(s, nrcuv);

	while (fgets(s, sizeof(s), stdin)) {
		nrcuv ++;
		transf(s, nrcuv);
	}

	sort(cuv + 1, cuv + nrcuv + 1);

	int nr = 0;
	for (i = 0; i < l1; i ++) {
		nr += (sir[i] - 'a') * trei[i];
	}

	int rez = 0, poz = 0;
	if (find(nr)) rez ++;

	for (i = l1; i < L; i ++) {
		nr -= (sir[poz] - 'a');
		nr /= 3;
		nr += ((sir[i] - 'a') * trei[l1 - 1]);
		poz ++;

		if (find(nr)) rez ++;
	}
	printf("%d\n", rez);

	return 0;
}