Cod sursa(job #343300)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 august 2009 14:26:04
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define MAX_N 100000005
#define MAX_M 1005

#define P 3
#define MOD 99987

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

char S[MAX_N];
int N, M, P1(1), H, Sol;

vector <int> G[MOD];

void insert(int x)
{
	int k = x % MOD;
	G[k].push_back(x);
}

int find(int x)
{
	int k = x % MOD;
	
	foreach(G[k])
		if(*it == x)
			return 1;
		
	return 0;
}

void citire()
{
	char s[MAX_M];
	
	fgets(S, MAX_N, stdin);
	N = strlen(S) - 1;
	
	while(fgets(s, MAX_M, stdin))
	{
		int h = 0;

		M = strlen(s) - 1;
		for(int i = 0; i < M; ++i)
			h = h * P + (s[i] - 'a');
		
		insert(h);
		//fprintf(stderr, "%d\n",h);
	}
}

void solve()
{
	for(int i = 0; i < M; ++i)
	{
		H = H * P + (S[i] - 'a');
		if(i)
			P1 *= P;
	}
	
	for(int i = M; i <= N; ++i)
	{
		//fprintf(stderr,"%d\n", H);
		Sol += find(H);
		
		H = (H - (S[i-M] - 'a')*P1) * P + (S[i] - 'a');
	}
	
	printf("%d\n",Sol);
}

int main()
{
	freopen("abc2.in","rt",stdin);
	freopen("abc2.out","wt",stdout);

	citire();
	solve();
}