Cod sursa(job #98444)

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

using namespace std;

#define NMAX 10000010
#define Q 101869

struct nod
{
	nod *next;
	long long x;
};

void read();
void add(long long x);

char S[NMAX];
nod H[Q];

int M, N;

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

	read();
	return 0;
}

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

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

	for(i = 0; i < Q; i++)
		H[i].x = -1;

	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';

		add(ok);
	}

	N = strlen(S);

	int rez = 0;

	la = 1;
	ok = 0;
	if(M <= N)
	for(i = 0; i < M; i++)
	{
		la = la * 3;
		ok = ok * 3 + S[i] - 'a';
	}

	la /= 3;

	nod *p;
	for(i = 0; i + M <= N; i++)
	{	
		for(p = H[ok % Q].next; p; p = p->next)
			if(p->x == ok)
			{
			rez++;
			break;
			}
		ok -= la * (S[i] - 'a');
		ok *= 3;
		if(i + M < N)
		ok += S[i + M] - 'a';
	}
	printf("%d\n", rez);
}

void add(long long x)
{
	nod *p, *r;

	for(p = &H[x % Q]; p->next; p = p->next)
		if(p->x == x)
			return;
		else if(p->x < x && (p->next->x) > x)
			 break;

	r = new nod;
	r->next = p->next;
	p->next = r;
	r->x = x;
}