Cod sursa(job #104524)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 16 noiembrie 2007 11:56:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.44 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];
unsigned int cuv[C_MAX];
int l1, L, nrcuv;
long long trei[L_MAX];

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

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

int find(long long 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

	scanf("%s\n", sir);
	L = strlen(sir);
	sir[L] = '\0';

	if (scanf("%s\n", s) != EOF) {
		l1 = strlen(s);

		nrcuv ++;
		transf(s, nrcuv);
	}

	while (scanf("%s\n", s) != EOF) {
		nrcuv ++;
		transf(s, nrcuv);
	}

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

		long long nr = 0;
		for (i = 0; i < l1; i ++) {
			nr += (long long) (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 += (long long) ((sir[i] - 'a') * trei[l1 - 1]);
			poz ++;

			if (find(nr)) rez ++;
		}

		printf("%d\n", rez);
	} else printf("0\n");

	return 0;
}