Cod sursa(job #98221)

Utilizator GiggityGlen Quagmire Giggity Data 10 noiembrie 2007 11:23:11
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.07 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

#define NMAX 10000010

void read();
int find(long long x);

vector<long long> V;
char S[NMAX];
int M, U, N;

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

	read();
	return 0;
}

void read()
{
	char A[32];
	long long ok;
	int i, j;

	M = -1;
	fgets(S, NMAX, stdin);
	S[strlen(S) - 1] = 0;

	for(;!feof(stdin);)
	{
		scanf("%s ", A);
		if(M == -1) M = strlen(A);

		ok = 0;
		for(i = 0; i < M; i++)
		ok = ok * 3 + A[i] - 'a';

		V.push_back(ok);
	}
	
	sort(V.begin(), V.end());
	U = V.size();

	N = strlen(S);
	int rez = 0;

	for(i = 0; i + M <= N; i++)
	{
		ok = 0;

		for(j = 0; j < M; j++)
		ok = ok * 3 + S[i + j] - 'a';
		
		if(find(ok))
			rez++;
	}
	printf("%d\n", rez);
}

int find(long long x)
{
	int i, step;

	for(step = 1; step <= U; step <<= 1);
	for(i = -1; step; step >>= 1)
		if(i + step < U && V[i + step] <= x)
			i += step;
	
	if(V[i] == x)
		return 1;
	return 0;
}