Cod sursa(job #103884)

Utilizator peanutzAndrei Homorodean peanutz Data 15 noiembrie 2007 18:50:29
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.62 kb
#include <stdio.h>
#include <string.h>
#include <memory.h>

#define NMAX 10000010

struct tri
{
	int list;
	struct tri *a, *b, *c;
};
typedef struct tri *trie;
trie t;

char s[NMAX];
char x[24];
int n, res;

void baga()
{
	int i = 0, until = n;
	trie crt = t;
	while(i < until)
	{
		if(x[i] == 'a')
		{
			if(crt -> a == NULL)
				crt -> a = new tri;
			crt  = crt -> a;
			crt -> list = i;
			crt -> a = crt -> b = crt -> c = NULL;
		}
		else if(x[i] == 'b')
		{
			if(crt -> b == NULL)
				crt -> b = new tri;
			crt = crt -> b;
			crt -> list = i;
			crt -> a = crt -> b = crt -> c = NULL;
		}
		else if(x[i] == 'c')
		{
			if(crt -> c == NULL)
				crt -> c = new tri;
			crt = crt -> c;
			crt -> list = i;
			crt -> a = crt -> b = crt -> c = NULL;
		}
		++i;
	}
}

short df(int i)
{
	trie crt = t;
	int until = i+n;
	while(i < until)
	{
		if(s[i] == 'a')
		{
			if(crt -> a == NULL)
				return 0;
			crt = crt -> a;
		}
		else if(s[i] == 'b')
		{
			if(crt -> b == NULL)
				return 0;
			crt = crt -> b;
		}
		else if(s[i] == 'c')
		{
			if(crt -> c == NULL)
				return 0;
			crt = crt -> c;
		}
	}
	return 1;
}

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

	t = new tri;
	t -> a = t -> b = t -> c = NULL;

	scanf("%s", s);

	scanf("%s", x);
	n = strlen(x);
	baga();
	while(!feof(stdin))
	{
		scanf("%s", x);
		baga();
	}
	for(int i = 0, until = strlen(s)-n; i <= until; ++i)
		res += df(i);
	
    printf("%d\n", res);
	return 0;
}