Cod sursa(job #103988)

Utilizator peanutzAndrei Homorodean peanutz Data 15 noiembrie 2007 20:30:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.96 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[21];
int n, res;

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

short df(int i)
{
	trie crt = t;
	int until = i+n;
	while(i < until)
	{
		if(s[i] == 'a')
		{
			if(!(crt -> a))
				return 0;
			crt = crt -> a;
//			printf("%d", crt -> list);
		}
		else if(s[i] == 'b')
		{
			if(!(crt -> b))
				return 0;
			crt = crt -> b;
//			printf("%d", crt -> list);
		}
		else if(s[i] == 'c')
		{
			if(!(crt -> c))
				return 0;
			crt = crt -> c;
//   			printf("%d", crt -> list);
		}
        ++i;
	}
	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("\n");
	
	printf("%d\n", res);
	return 0;
}